náhled|upright=1.2|Petersenův graf (vlevo) a jeho komplement (vpravo)
Komplement nebo doplněk grafu je graf, který má stejný počet vrcholů a mezi nimi právě ty hrany, které v původním grafu chybí.
Komplement grafu je tedy graf pro který platí: A pro každé dva různé vrcholy platí právě tehdy pokud . Graf je tedy úplným grafem.
Grafy a se nazývají komplementární grafy.
Vlastnosti Komplement úplného grafu je graf bez hran. Komplement triviálního grafu je triviální graf.
Reference
Externí odkazy
Kategorie:Teorie grafů