Hoppa till innehållet

Komplementgraf

Från Wikipedia
Ett enkelt exempel på komplementgrafer.
Petersens graf (vänster) och dess komplement (höger).

En komplementgraf är inom matematik, specifikt grafteori, en graf som konstrueras utifrån en given graf G genom att låta graferna ha samma nodmängd, men att två noder i komplementgrafen har en båge mellan sig om och endast om de inte har en båge mellan sig i G.

Konstruktion

[redigera | redigera wikitext]

Om är en graf och K består av alla delmängder av N med två element så är komplementgrafen till G:

Observera att en komplementgraf inte är detsamma som ett mängdteoretiskt komplement.

Flera grafteoretiska koncept är varandras motsatser sett i komplementgrafer. En bågfri grafs komplementgraf är en komplett graf, en oberoende mängd i en graf blir en klick i dess komplementgraf, en triangelfri graf blir en klofri graf.

  • Eriksson, Kimmo; Hillevi Gavel (2002). Diskret matematik och diskreta modeller. Studentlitteratur. ISBN 91-44-02465-7 
  • Bollobás, Béla (2002). Modern Graph Theory. Springer Verlag. ISBN 978-0387984889