Komplementgraf

Från Wikipedia
Hoppa till: navigering, sök
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 G=(N,B) är en graf och K består av alla delmängder av N med två element så är komplementgrafen till G:

\overline{G} = (N, B \setminus K).

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

Användning[redigera | redigera wikitext]

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.

Referenser[redigera | redigera wikitext]

  • 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