Komplement grafu

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 ${\displaystyle G\ }$ je tedy graf ${\displaystyle G_{0}\ }$ pro který platí: ${\displaystyle V=V_{0}\ }$ A pro každé dva různé vrcholy ${\displaystyle u,\ v}$ platí ${\displaystyle {u,v}\in E}$ právě tehdy pokud ${\displaystyle {u,v}\notin E_{0}}$. Graf ${\displaystyle G_{1}=(V,E\cup E_{0})}$ je tedy úplným grafem.

Grafy ${\displaystyle G\ }$ a ${\displaystyle G_{0}\ }$ se nazývají komplementární grafy.

• Komplement úplného grafu je graf bez hran.
• Komplement triviálního grafu je triviální graf.

V tomto článku byl použit překlad textu z článku Komplement grafu na slovenské Wikipedii.

• Obrázky, zvuky či videa k tématu komplement grafu na Wikimedia Commons

Tento článek je příliš stručný nebo postrádá důležité informace. Pomozte Wikipedii tím, že jej vhodně rozšíříte. Nevkládejte však bez oprávnění cizí texty.