Komplement grafu

Komplement grafu nebo doplněk grafu $G\$ je 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.

Petersenův graf (vlevo) a jeho komplement (vpravo)

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.