Rovinný graf: Porovnání verzí
Smazaný obsah Přidaný obsah
základ |
m pár menších úprav, wiki apod., ale matematika na začátku pořád není úplně ideální… |
||
Řádek 1:
'''Rovinný graf''' je [[graf]], pro který existuje takové '''rovinné nakreslení''', že se žádné dvě hrany nekříží
== Rovinné nakreslení ==
''Oblouk'' je [[podmnožina]] [[rovina|roviny]] tvaru <math>\sigma(<0,1>)</math>, kde <math>\sigma: [0, 1] \rightarrow \mathbb{R}^2</math> je nějaké [[spojité zobrazení|spojité]] a [[prosté zobrazení|prosté]] (až na koncové body) [[zobrazení]] [[interval (matematika)|intervalu]]
''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 <math>\sigma(i)</math> a <math>\sigma(j)</math>. 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''. <BR>▼
Topologický graf je rovinný, pokud libovolné dva oblouky odpovídající hranám ''e'' a ''f'' (<math>e \ne f\;</math>) mají společné nejvýše koncové body.▼
▲''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 <math>\sigma(i)</math> a <math>\sigma(j)</math>. 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''.
== Stěna grafu ==▼
Nechť <math>A\subseteq\mathbb{R}^2</math> je nějaká podmnožina roviny. Nazveme ji ''souvislou'', pokud pro <math>\forall x, y \in A\;</math> platí, že existuje oblouk ''o'' s koncovými body ''x'' a ''y'' takový, že <math>o\subseteq A</math>. 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.▼
▲Topologický graf je rovinný, pokud libovolné dva oblouky odpovídající hranám ''e'' a ''f'' (
▲== Stěna grafu ==
▲Nechť <math>A\subseteq\mathbb{R}^2</math> je nějaká podmnožina roviny. Nazveme ji ''souvislou'', pokud pro <math>\forall x, y \in A
== Charakterizace rovinných grafů ==
=== [[Kazimierz Kuratowski|Kuratowského]] věta ===
Graf ''G'' je rovinný právě tehdy, není-li žádný jeho [[podgraf]] izomorfní [[dělení grafu]] <math>K_5</math> ani <math>K_{3, 3}</math>. (<math>K_5</math> označuje [[úplný graf]] na pěti vrcholech, <math>K_{3, 3}</math> pak úplný [[bipartitní graf]].)
▲| <math>K_4</math>'', úplný graf na 4 vrcholech, lze zakreslit do roviny bez křížení hran. Pro ''<math>K_5</math> ''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
▲Obrázek ukazuje graf <math>K_4</math> 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
Z prvního tvrzení vyplývá důležitý fakt, a to, že každý rovninný graf má alespoň jeden [[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 5.
== Podívejte se také na ==
*[[Duální graf]]
*[[Barvení grafu]]
[[Kategorie:Teorie grafů]]▼
[[de:Planarer Graph]]
Řádek 45 ⟶ 42:
[[pt:Grafo planar]]
[[th:กราฟเชิงระนาบ]]
▲[[Kategorie:Teorie grafů]]
| |||