Komplement grafu

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 $G\$ je tedy graf $G_{0}\$ pro který platí: $V=V_{0}\$ A pro každé dva různé vrcholy $u,\ v$ platí ${u,v}\in E$ právě tehdy pokud ${u,v}\notin E_{0}$. Graf $G_{1}=(V,E\cup E_{0})$ je tedy úplným grafem.

Grafy $G\$ a $G_{0}\$ 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

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

Externí odkazy

• Obrázky, zvuky či videa k tématu Komplement grafu na Wikimedia Commons