Loading AI tools
Från Wikipedia, den fria encyklopedin
En oberoende mängd är inom matematik, specifikt grafteori, en mängd av noder M i en graf G sådan att det inte finns någon båge i G mellan någon av noderna i M. Ekvivalent uttryckt så är mängden M oberoende om varje båge i G har högst en ändpunkt som ligger i M. Med storleken på en oberoende mängd avses antalet noder som mängden innehåller.
En maximal oberoende mängd är en oberoende mängd sådan att om man lägger till en nod i mängden är den inte oberoende längre. En största oberoende mängd är en oberoende mängd sådan att det inte finns någon oberoende mängd som har fler noder. Storleken på en största oberoende mängd kallas grafens oberoendetal.
Även när det gäller bågar i grafer talas det om oberoende mängder, dessa kallas vanligtvis matchningar.
Problemet att avgöra om en given graf har en oberoende mängd av en given storlek kallas för oberoende mängd-problemet. Att hitta en oberoende mängd är ekvivalent med att hitta en klick i komplementgrafen, så oberoende mängd-problemet är relaterat till klickproblemet. Både oberoende mängd-problemet och klickproblemet är NP-fullständiga.
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.