Komplement grafu

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie
Petersenov graf (vľavo) a jeho komplement (vpravo)

Komplement grafu alebo doplnok grafu G\ je graf G_0\ pre ktorý platí: V = V_0\ a pre každé dva rôzne vrcholy u,\ v platí {u, v} \isin E práve vtedy ak {u, v} \notin E_0. Graf G_1 = (V, E \cup E_0) je teda úplným grafom.

Grafy G\ a G_0\ sa nazývajú komplementárne grafy.

Vlastnosti[upraviť | upraviť zdroj]

  • Komplement úplného grafu je graf bez hrán.
  • Komplement triviálneho grafu je triviálny graf.