Procházet otázky :: SZZ na MFF UK

#

- Hlavní strana
- Okruhy
- Projít
- Stáhnout
- Co je potřeba
- Chci přispět
- Kredity

Hledat:

## Prohlížení státnicových textů

## Rovinné grafy

Definice (Oblouk)

Oblouk je podmnožina roviny tvaru , kde je nějaké prosté spojité zobrazení intervalu do roviny. Přitom body a nazýváme koncové body oblouku .

Definice (Nakreslení grafu)

Nakreslením grafu rozumíme přiřazení, které každému vrcholu v grafu přiřazuje bod roviny a každé hraně přiřazuje oblouk v rovině s koncovými body a Zobrazení je prosté (různým vrcholům odpovídají různé body) a žádný z bodů tvaru není nekoncovým bodem žádného z oblouků Graf spolu s nakreslením nazýváme topologický graf.

Definice (Rovinný graf)

Nakreslení grafu v němž oblouky odpovídající různým hranám mají společné nanejvýš koncové body, se nazývá rovinné nakreslení. Graf je rovinný, má-li alespoň jedno rovinné nakreslení.

Definice (Stěna grafu)

Mějme rovinný topologický graf. Množinu bodů roviny (kde je množina všech bodů všech oblouků nakreslení grafu ) nazveme souvislou, pokud pro libovolné dva body existuje oblouk s koncovými body Relace souvislosti rozdělí množinu všech bodů roviny, které neleží v žádném z oblouků nakreslení, na třídy ekvivalence. Ty nazýváme stěnami topologického rovinného nakreslení grafu .

Definice (Topologická kružnice)

Uzavřená křivka v rovině neprotínající sebe sama; formálně se definuje jako oblouk, jehož koncové body splývají.

Věta (Jordanova, o kružnici)

Každá topologická kružnice rozděluje rovinu na právě dvě souvislé části (vnitřek a vnějšek), přičemž je jejich společnou hranicí.

Věta (Kuratowského)

Graf je rovinný, právě když žádný jeho podgraf není isomorfní dělení grafu ani

Věta (Eulerův vzorec)

Nechť je souvislý rovinný graf, a nechť je počet stěn nějakého rovinného nakreslení Potom platí

Důkaz

Indukcí podle počtu hran. Pro graf sestávající pouze z jednoho vrcholu vzorec platí.

1. Pokud přidaná hrana nevytvoří kružnici, nezměnil se počet stěn, ale o jednu se zvětšil počet vrcholů a hran (graf musí být vždy souvislý, takže jediná možnost jak tohoto dosáhnout, je připojit další vrchol).
2. Pokud přidaná hrana vytvoří kružnici, zvětší se počet stěn o jednu (přidaná hrana sousedí se dvěma různými stěnami -- podle Jordanovy věty o kružnici -- které před přidáním byly stěnou jedinou), počet hran také o jednu, a počet vrcholů se nezmění.

Vzorec tedy v obou případech platí.

Věta (2-souvislý rovinný graf)

Dvousouvislý rovinný graf má hranice libovolné stěny libovolného nakreslení jako kružnice.

Věta (Maximální počet hran rovinného grafu)

Nechť je rovinný graf s alespoň 3 vrcholy. Potom Rovnost nastává pro každý maximální rovinný graf, t.j. rovinný graf, ke kterému nelze již přidat žádnou hranu (při zachování množiny vrcholů) tak, aby zůstal rovinný. Pokud graf navíc neobsahuje trojúhelník (t.j. jako podgraf) a má-li alespoň 3 vrcholy, potom

Důkaz

Obě tvrzení můžeme dokázat pro maximální rovinný graf. V prvním případě je určitě dvousouvislý, protože jinak můžu ještě nějaké dva body spojit. Navíc každá stěna musí být trojúhelník (je-li čtverec nebo něco většího, také jdou ještě nějaké dva body spojit). Tím dostanu, že a zbytek vyjde z Eulerova vzorce.

Druhý případ má jednu zvláštnost - takový graf může být hvězda. Pro tu je ale tvrzení splněno. Pokud není hvězda, už musí být dvousouvislý a všechny stěny musí být čtverce, takže dostanu a z Eulerova vzorce i celý výsledek.

Důsledek

Rovinný graf má alespoň jeden vrchol stupně nejvýše 5.