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).

KonstruktionRedigera

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.

AnvändningRedigera

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.

ReferenserRedigera

  • 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