Rovinný graf: Porovnání verzí
Smazaný obsah Přidaný obsah
m robot přidal: ca:Graf planar |
Chromatické číslo rovinného grafu je max. 4, nie 5, ako bolo uvedené. |
||
Řádek 26:
Je-li ''G = (V, E)'' rovinný graf, pak platí, že <math>|E|\le 3|V| - 6</math>. Neobsahuje-li navíc tento graf jako podgraf trojúhelník (tj. <math>K_3</math>, úplný graf na 3 vrcholech), pak <math>|E|\le 2|V| - 4</math>.
Z prvního tvrzení vyplývá důležitý fakt, a to, že každý rovinný graf má alespoň jeden [[Graf (teorie grafů)#Základní pojmy|vrchol]] [[stupeň vrcholu|stupně]] nejvýše 5. Díky tomuto faktu lze následně dokázat, že [[chromatické číslo]] každého rovinného grafu je nejvýše
== Související články ==
|