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 $\sigma (\langle 0,1\rangle )$, kde $\sigma :[0,1]\rightarrow \mathbb {R} ^{2}$ je nějaké spojité a prosté (až na koncové body) zobrazení intervalu $\langle 0,1\rangle$ do roviny. Body $\sigma (0)$ a $\sigma (1)$ se nazývají koncové body oblouku.

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

Stěna grafu

Nechť $A\subseteq \mathbb {R} ^{2}\setminus X$ (kde $X$ je množina všech bodů a všech oblouků nakreslení grafu). Nazveme ji souvislou, pokud pro $\forall x,y\in A$ platí, že existuje oblouk $o$ s koncovými body $x$ a $y$ takový, že $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 $K_{5}$ nebo $K_{3,3}$. ($K_{5}$ označuje úplný graf na pěti vrcholech, $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 $G=(V,E)$ souvislý rovinný graf, pak $|V|-|E|+s=2$, kde $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 $G=(V,E)$ rovinný graf, pak platí, že $|E|\leq 3|V|-6$. Neobsahuje-li navíc tento graf jako podgraf trojúhelník (tj. $K_{3}$, úplný graf na 3 vrcholech), pak $|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