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.

Externí odkazy

• Šablona:Commonscat