Oberoende mängd

De 9 blåa noderna är en maximal oberoende mängd i den här grafen av 24 noder.

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.

Egenskaper

• En mängd är oberoende i en graf om och endast om den bildar en klick i komplementgrafen.
• En mängd är oberoende om och endast om dess komplement är en kanttäckning.
• Varje maximal oberoende mängd är en dominerande mängd.

Oberoende mängd-problemet

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.

Referenser

• Bollobás, Béla (2002). Modern Graph Theory. Springer Verlag. ISBN 978-0387984889 
• Godsil, Chris; Gordon Royle (2001). Algebraic Graph Theory. Springer Verlag. ISBN 0-387-95241-1 
• Cormen, Thomas H.; Charles E. Leiserson, Ronald L. Rivest, Clifford Stein (2001). Introduction to Algorithms. MIT Press. ISBN 0-07-013151-1