Rovinný graf

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

Obsah

1 Rovinné nakreslení
2 Stěna grafu
3 Charakterizace rovinných grafů
4 Související články

[editovat] Rovinné nakreslení

Oblouk je podmnožina roviny tvaru $σ( < 0,1 > )$ , kde $\sigma: [0, 1] \rightarrow \mathbb{R}^2$ je nějaké spojité a prosté (až na koncové body) zobrazení intervalu <0, 1> do roviny. Body $σ(0)$ a $σ(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 $σ(i)$ a $σ(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 ≠ f) mají společné nejvýše koncové body.

[editovat] Stěna grafu

Nechť $A\subseteq\mathbb{R}^2$ je nějaká podmnožina roviny. 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.

[editovat] Charakterizace rovinných grafů

[editovat] Kuratowského věta

Graf G je rovinný právě tehdy, není-li žádný jeho podgraf izomorfní dělení grafu $K 5$ ani $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í.

[editovat] Eulerův vzorec

Pro rovinné grafy také platí následující vzorec, je to ovšem pouze implikace: Je-li G = (V, E) 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.

[editovat] Maximální počet hran

Je-li G = (V, E) rovinný graf, pak platí, že $|E|\le 3|V| - 6$ . Neobsahuje-li navíc tento graf jako podgraf trojúhelník (tj. $K 3$ , úplný graf na 3 vrcholech), pak $|E|\le 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. Díky tomuto faktu lze následně dokázat, že chromatické číslo každého rovinného grafu je nejvýše 5.

[editovat] Související články

Kategorie: Typy grafů

Rovinný graf v jiných jazycích: العربية, Deutsch, English, Español, Français, עברית, Magyar, Italiano, 日本語, 한국어, Lietuvių, ‪Norsk (nynorsk)‬, Polski, Português, Русский, ไทย, Tiếng Việt, 中文

Tento článek je převzat z české wikipedie - otevřené encyklopedie, originální článek naleznete na adrese: „http://cs.wikipedia.org/wiki/Rovinn%C3%BD_graf“
Stránka byla naposledy upravena v Stránka byla naposledy editována 17. 6. 2008 v 23:09.
Veškerý text je dostupný za podmínek GNU Free Documentation License (Autorské právo pro podrobnosti).