cs.wikipedia.org

Rovinný graf – Wikipedie

Z Wikipedie, otevřené encyklopedie

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

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.

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.

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.)

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

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 K4 se 4 vrcholy, 6 hranami a vyznačenými 4 stěnami. Eulerův vztah platí, 4 − 6 + 4 = 2.

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.

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