Komplementgraf
Hoppa till navigering
Hoppa till sök
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
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ä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.