Komplement grafu

Z Wikipedie, otevřené encyklopedie
Skočit na navigaci Skočit na vyhledávání
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[editovat | editovat zdroj]

  • Komplement úplného grafu je graf bez hran.
  • Komplement triviálního grafu je triviální graf.

Reference[editovat | editovat zdroj]

V tomto článku byl použit překlad textu z článku Komplement grafu na slovenské Wikipedii.