Komplementgraf

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.

Ett enkelt exempel på komplementgrafer.

Petersens graf (vänster) och dess komplement (höger).

Konstruktion

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

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

• 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