Rovinný graf: Porovnání verzí

''Oblouk'' je [[podmnožina]] [[rovina|roviny]] tvaru <math>\sigma(<\langle 0,1> \rangle)</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í (matematika)|zobrazení]] [[interval (matematika)|intervalu]] <math>\langle 0,&nbsp; 1 \rangle</math> do roviny. Body <math>\sigma(0)</math> a <math>\sigma(1)</math> se nazývají ''koncové body'' oblouku.

''Rovinné nakreslení'' je pak zobrazení ''<math>b''</math>, které každému vrcholu ''<math>v''</math> přiřazuje bod roviny ''<math>b(v)''</math> a hraně ''<math>{i, j}''</math> 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 ''<math>b(v)''</math> 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 ''<math>e''</math> a ''<math>f''</math> (''<math>e''&nbsp;≠&nbsp;'' \ne f''</math>) mají společné nejvýše koncové body.

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 ''<math>o''</math> s koncovými body ''<math>x''</math> a ''<math>y''</math> takový, že <math>o\subseteq A</math>. Oblouky příslušné hranám nějakého topologického grafu pak podle této [[Binárníbinární relace|relace]] souvislosti rozdělují rovinu na [[třída ekvivalence|třídy ekvivalence]], které se nazývají ''stěny'' grafu.

Je-li ''<math>G''&nbsp; =&nbsp;'' (V,&nbsp; E)''</math> souvislý rovinný graf, pak <math>|V| - |E| + s = 2</math>, kde ''<math>s''</math> je počet stěn nějakého rovinného nakreslení tohoto grafu.

Je-li ''<math>G&nbsp; =&nbsp; (V,&nbsp; E)''</math> rovinný graf, pak platí, že <math>|E|\le 3|V| - 6</math>. Neobsahuje-li navíc tento graf jako podgraf trojúhelník (tj. <math>K_3</math>, úplný graf na 3 vrcholech), pak <math>|E|\le 2|V| - 4</math>.