Komplement grafu

z Wikipédie, slobodnej encyklopédie
Petersenov graf (vľavo) a jeho komplement (vpravo)

Komplement grafu alebo doplnok grafu je graf pre ktorý platí: a pre každé dva rôzne vrcholy platí práve vtedy ak . Graf je teda úplným grafom.

Grafy a 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.