Rovinný graf

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

Rovinné nakreslení

Oblouk je podmnožina roviny tvaru ${\displaystyle \sigma (\langle 0,1\rangle )}$, kde ${\displaystyle \sigma$ :[0,1]\rightarrow \mathbb {R} ^{2}} je nějaké spojité a prosté (až na koncové body) zobrazení intervalu ${\displaystyle \langle 0,1\rangle }$ do roviny. Body ${\displaystyle \sigma (0)}$ a ${\displaystyle \sigma (1)}$ se nazývají koncové body oblouku.

Rovinné nakreslení je pak zobrazení ${\displaystyle b}$, které každému vrcholu ${\displaystyle v}$ přiřazuje bod roviny ${\displaystyle b(v)}$ a hraně ${\displaystyle {i,j}}$ přiřadí oblouk s koncovými body ${\displaystyle \sigma (0)=b(i)}$ a ${\displaystyle \sigma (1)=b(j)}$. Zobrazení je prosté (různým vrcholům odpovídají různé body roviny) a žádný bod ${\displaystyle b(v)}$ 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 ${\displaystyle e}$ a ${\displaystyle f}$ (${\displaystyle e\neq f}$) mají společné nejvýše koncové body.

Stěna grafu

Nechť ${\displaystyle A\subseteq \mathbb {R} ^{2}\setminus X}$ (kde ${\displaystyle X}$ je množina všech bodů a všech oblouků nakreslení grafu). Nazveme ji souvislou, pokud pro ${\displaystyle \forall x,y\in A}$ platí, že existuje oblouk ${\displaystyle o}$ s koncovými body ${\displaystyle x}$ a ${\displaystyle y}$ takový, že ${\displaystyle o\subseteq A}$. 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ů

Kuratowského věta

Graf G je rovinný právě tehdy, není-li žádný jeho podgraf izomorfní s nějakým dělením grafu ${\displaystyle K_{5}}$ nebo ${\displaystyle K_{3,3}}$. (${\displaystyle K_{5}}$ označuje úplný graf na pěti vrcholech, ${\displaystyle K_{3,3}}$ pak úplný bipartitní graf.)

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

Eulerův vzorec

Pro rovinné grafy také platí následující vzorec, je to ovšem pouze implikace: Je-li ${\displaystyle G=(V,E)}$ souvislý rovinný graf, pak ${\displaystyle |V|-|E|+s=2}$, kde ${\displaystyle s}$ je počet stěn nějakého rovinného nakreslení tohoto grafu.

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

Maximální počet hran

Je-li ${\displaystyle G=(V,E)}$ rovinný graf, pak platí, že ${\displaystyle |E|\leq 3|V|-6}$. Neobsahuje-li navíc tento graf jako podgraf trojúhelník (tj. ${\displaystyle K_{3}}$, úplný graf na 3 vrcholech), pak ${\displaystyle |E|\leq 2|V|-4}$.

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ánky

• Duální graf
• Barvení grafu

Externí odkazy

• Obrázky, zvuky či videa k tématu rovinný graf na Wikimedia Commons