Komplement grafu: Porovnání verzí

Přidány 3 bajty ,  před 2 lety
m
přesun šablony pahýl dospod; kosmetické úpravy
("Lidské" vysvětlení na začátek - jsme encyklopedie)
m (přesun šablony pahýl dospod; kosmetické úpravy)
[[Soubor:Complement_graph_sample.png|thumbnáhled|upright=1.2|[[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 <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]].
 
Grafy <math>G\ </math> a <math>G_0\ </math> 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}}
 
== Reference ==
{{Překlad|jazyk = sk|článek = Komplement grafu|revize = 5904160}}
 
{{Pahýl}}
 
[[Kategorie:Teorie grafů]]
135 209

editací