Komplement grafu: Porovnání verzí
Smazaný obsah Přidaný obsah
"Lidské" vysvětlení na začátek - jsme encyklopedie |
m přesun šablony pahýl dospod; kosmetické úpravy |
||
Řádek 1:
[[Soubor:Complement_graph_sample.png|
'''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.
== Reference ==
{{Překlad|jazyk = sk|článek = Komplement grafu|revize = 5904160}}
{{Pahýl}}
[[Kategorie:Teorie grafů]]
|