Otevřít hlavní menu

Rovinný graf (též planární graf) je graf, pro který existuje takové rovinné nakreslení, že se žádné dvě hrany nekříží.

Obsah

Rovinné nakresleníEditovat

Oblouk je podmnožina roviny tvaru  , kde   je nějaké spojité a prosté (až na koncové body) zobrazení intervalu   do roviny. Body   a   se nazývají koncové body oblouku.

Rovinné nakreslení je pak zobrazení  , které každému vrcholu   přiřazuje bod roviny   a hraně   přiřadí oblouk s koncovými body   a  . Zobrazení je prosté (různým vrcholům odpovídají různé body roviny) a žádný bod   není nekoncovým bodem žádného oblouku. Graf spolu s takovýmto zobrazením nazveme topologický graf.

Topologický graf je rovinný, pokud libovolné dva oblouky odpovídající hranám   a   ( ) mají společné nejvýše koncové body.

Stěna grafuEditovat

Nechť   (kde   je množina všech bodů a všech oblouků nakreslení grafu). Nazveme ji souvislou, pokud pro   platí, že existuje oblouk   s koncovými body   a   takový, že  . Oblouky příslušné hranám nějakého topologického grafu pak podle této relace souvislosti rozdělují rovinu na třídy ekvivalence, které se nazývají stěny grafu.

Charakterizace rovinných grafůEditovat

Kuratowského větaEditovat

Graf G je rovinný právě tehdy, není-li žádný jeho podgraf izomorfní dělení grafu   ani  . (  označuje úplný graf na pěti vrcholech,   pak úplný bipartitní graf.)

 
K4, úplný graf na 4 vrcholech, lze zakreslit do roviny bez křížení hran. Pro K5 to možné není.

Eulerův vzorecEditovat

Pro rovinné grafy také platí následující vzorec, je to ovšem pouze implikace: Je-li   souvislý rovinný graf, pak  , kde   je počet stěn nějakého rovinného nakreslení tohoto grafu.

 
Příklad ukazuje graf K4 se 4 vrcholy, 6 hranami a vyznačenými 4 stěnami. Eulerův vztah platí, 4 − 6 + 4 = 2.

Maximální počet hranEditovat

Je-li   rovinný graf, pak platí, že  . Neobsahuje-li navíc tento graf jako podgraf trojúhelník (tj.  , úplný graf na 3 vrcholech), pak  .

Z prvního tvrzení vyplývá důležitý fakt, a to, že každý rovinný graf má alespoň jeden vrchol stupně nejvýše 5.

Související článkyEditovat