Komplement grafu: Porovnání verzí

Smazaný obsah Přidaný obsah

V textu

Verze z 15. 8. 2015, 22:12

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.

Pahýl

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.

Reference

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

@@ Řádek 1: / Řádek 1: @@
-[[Soubor:Complement_graph_sample.png|thumb|right|[[Petersenův graf]] (vlevo) a jeho komplement (vpravo)]]
+[[Soubor:Complement_graph_sample.png|thumb|upright=1.2|[[Petersenův graf]] (vlevo) a jeho komplement (vpravo)]]
-'''Komplement grafu''' nebo '''doplněk grafu''' <math>G\ </math> je graf <math>G_0\ </math> pro který platí:
+'''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 <math>G\ </math> je tedy graf <math>G_0\ </math> pro který platí:
 <math>V = V_0\ </math> A pro každé dva různé vrcholy <math>u,\ v</math> platí <math>{u, v} \isin E</math> právě tehdy pokud <math>{u, v} \notin E_0</math>. Graf <math>G_1 = (V, E \cup E_0)</math> je tedy [[Úplný graf|úplným grafem]].