Komplementgraf
Utseende
![](http://178.128.105.246/host-http-upload.wikimedia.org/wikipedia/commons/thumb/e/e2/Complement_graph.svg/200px-Complement_graph.svg.png)
![](http://178.128.105.246/host-http-upload.wikimedia.org/wikipedia/commons/thumb/d/d0/Complement_graph_sample.png/250px-Complement_graph_sample.png)
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.
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