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} \isin 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

Externí odkazy

Kategorie:Teorie grafů