Vnějškově rovinné grafy
Úloha číslo: 3279
Dokažte, že graf je vnějškově rovinný právě tehdy, když neobsahuje podrozdělení \(K_4\) a \(K_{2{,}3}\) jako podgraf.
Graf je vnějškově rovinný, pokud má rovinné nakreslení takové, že všechny vrcholy jsou incidentní s vnější stěnou.
Nápověda
Přidej apexový vrchol (vrchol spojený se všemi ostatními) a převeď na rovinnost.
Řešení
Mějme graf \(G\), který neobsahuje \(K_4\) a \(K_{2{,}3}\). Vytvoříme z něj graf \(G'\) přidáním jednoho nového vrcholu \(v\) spojeného hranou se všemi ostatními. Graf \(G'\) neobsahuje podrozdělení \(K_5\) ani \(K_{3{,}3}\). Tudíž je rovinný a můžeme ho nakreslit tak, aby \(v\) byl incidentní s vnější stěnou. Pak stačí \(v\) odebrat a získáme nakreslení vnějškové rovinné nakreslení \(G\), protože každý vrchol bude incidentní s vnější stěnou.
Ještě ukážeme druhou implikaci. Mějme vnějškově rovinný graf \(G\). Chceme ukázat, že neobsahuje podrozdělení \(K_4\) ani \(K_{2{,}3}\). Sporem nechť obsahuje. Vezměme vnějškové rovinné nakreslení \(G\) a do vnější stěny přidejme vrchol \(v\) spojený se všemi vrcholy grafu \(G\). Výsledný graf bude rovinný. Navíc ale bude obsahovat podrozdělení \(K_5\) nebo \(K_{3{,}3}\) a to je spor s Kuratowského větou, že rovinné grafy neobsahují podrozdělení \(K_5\) ani \(K_{3{,}3}\).
Varianta
Dokažte uvedenou charakterizaci vnějškově rovinných grafů bez užití Kuratowského věty.
Řešení
Dopředná implikace: \(K_4\) ani \(K_{2{,}3}\) nelze nakreslit jako vnějškově roviné, prootže vnější cyklus vždy odděluje zbylý vrchol.
Nahrazení cest hranami zachová vnějškovou rovinnost. Kdyby bylo vnějškově rovinné dělení \(K_4\), byl by vnějškově rovinný i samotný \(K_4\). Podobně pro \(K_{2{,}3}\). Proto vnějškově rovinný graf nemůže mít dělení \(K_4\) ani \(K_{2{,}3}\).
Zpětnou implikaci dokážeme indukcí podle počtu hran. Spojení vnějškově rovinných nakreslení mostem nebo artikulací zachová vnějškovou souvislost. Bez újmy na obecnosti se můžeme omezit na dvousouvislé grafy. Ty lze vytvořit z cyklů přidáváním uší.
Základ indukce, cykly, jsou vnějškově rovinné.
Nalezneme v \(G\) ucho. Podle indukčního předpokladu má \(G\) po odebrání ucha vnějškově rovinné nakreslení. Protože je tento graf dvousouvislý, tak je vnější stěna omezena cyklem. Mohou nastat následující případy:
- Ucho má délku alespoň dvě a spojuje sousední vrcholy cyklu, potom ho nakreslíme k vnější straně této hrany.
- Ucho má délku alespoň dvě a spojuje nesousední vrcholy cyklu, potom \(G\) má dělení \(K_{2{,}3}\) a tudíž tento případ nemůže nastat.
- Ucho je hrana a spojuje nesousední vrcholy cyklu ze stejné vnitřní stěny, potom ho nakreslíme do této stěny.
- Ucho je hrana a spojuje nesousední vrcholy cyklu v různých vnitřních stěnách, potom \(G\) má dělení \(K_4\) a tudíž tento případ nemůže nastat.