NDMI012/Zkouška 2013-02-07 Jelínek

Dnes se slosováním sešly hned dvě otázky z topologické teorie grafů

Kuratowskiho věta znění + důkaz
doplňující dotazy:

implikace Rovinné grafy neobsahují dělení $K_5, K_{3,3}$ [napsal jsem jen viz první ročník, ale musel jsem aspoň trochu rozvést - přes počítání dvěma způsoby počet dvojic (hrana, přilehlá stěna) pro obecné a triangle-free grafy]
Graf se zkontrahovanou hranou 3-souvislého grafu (viz Lemma o kontrahovatelné hraně) opět neobsahuje dělení $K_5, K_{3,3}$ - potřebné pro indukční předpoklad [viz Valla T., Matoušek J.: Skripta z KG1. Jde jen o rozbor případů]
Hranice stěny, v níž se nachází "kontrakční" vrchol $v_e$ , tvoří kružnici. [Jinak by hranice obsahovala separátor velikosti menší než tři, což je ve sporu s 3-souvislostí. Konkrétně bez $v_e$ vznikne 2-souvislý graf, ten se v důsledku Ušatého lemmatu dá nakreslit s kružnicovými hranicemi stěn.]
Ekvivalence s $K_5, K_{3,3}$ jako zakázanými minory - tj. verse z přednášky zahrnující i Wagnerovu větu [implikace bez minoru $\Rightarrow$ bez dělení, páč dělení je speciální případ minoru + implikace rovinný $\Rightarrow$ bez minoru, neb rovinné jsou uzavřené na minory.]

Nalezněte dvě NEisomorfní nakreslení $K_5$ na torus.
Nakreslení jsou isomorfní iff existuje grafový automorfismus převádějící každou hranici stěny na hranici stěny.

[
Torus representován polygonem $aba^{-1}b^{-1}$

nakreslení: "poštovní obálka" - tj. čtverec s úhlopříčkami, vrcholy jsou utvořeny rohy čtverce a průsečíkem diagonál. Pravý horní roh spojen s dolním levým přes hranu $a$ . Obdobně pravý dolní roh napojen přes $b$ s levý horním.
nakreslení: To samé s tím rozdílem, že hrana spojující oba horní rohy je vedena přes $a$ .

Invariant zachovaný při isomorfismu dvou nakreslení: každý vrchol "vidí" na stejné typy stěn. Formálně řečeno: Bipartitní grafy příslušných nakreslení s partitou všech vrcholů a s partitou všech stěn, jejichž hrany tvoří incidence vrcholů a stěn, jsou navzájem isomorfní.

Tento invariant není zachován u zmíněných nakreslení, poněvadž "průsečík úhlopříček" v prvním nakreslení vidí pouze stěny s trojúhelníkovou hranicí; naproti tomu v druhém nakreslení vidí všechny (!) vrcholy i na netrojúhelníkovou stěnu.
]

doplňující dotazy:

Jak poznat, které oblasti v polygonu jsou součástí jedné stěny? Tenhle dotaz vznikl, protože jsem sám měl měl potíže se správným určením. [Vybereme libovolný bod oblasti a podíváme se, kam všude se s ním dá dostat. Stěna je jednoduše taková "spojitá" komponenta souvislosti.]
Lze to vyřešit pomocí dvou nakreslení s různými počty stěn? [Ne, pokud jsou povolená jen buňková nakreslení. Ze zobecněné Eulerovy formule bychom museli pro jiný počet stěn nalézt nebuňkové nakreslení $K_5$ na torus. Viz dále]
*Jak vypadají nebuňkové stěny pro nakreslení souvislých grafů na toru? * Tedy stěny nehomeomorfní otevřenému disku. [Jediná možnost je stěna vzniklá nakreslením cyklu přes hrdlo toru, homeomorfní plášti válce bez obou podstav.]
Existuje nebuňkové nakreslení $K_5$ na torus? [Z předchozího bodu: takové nakreslení by musel mít 5-cyklus "vedoucí vodorovně" skrz okraj $a$ v polygonu $aba^{-1}b^{-1}$ a nesměl by mít hrany vedoucí přes hrany $b, b^{-1}$ . Tím bychom si totiž zrušili nebuňkovou stěnu. Po několika marných pokusech uvidíme, že to jaksi nejde.]
Jak dokázat, že neexistuje dotyčné nebuňkové nakreslení? [Pozor! Plášť boku válce není homeomorfní sféře, jelikož obsahuje nestažitelnou smyčku (přes hrdlo). Žádnou takovu však sféra nemá, proto nelze hned použít Kuratowskiho větu.

Lze však elegantně obejít takto: nakreslitelnost grafu na plochu válce bez podstav je ekvivalentní nakreslitelnosti stejného grafu na celou plochu válce (stačí to místo přes podstavy nakreslit dostatečně blízko k okrajům). Plocha válce je již očividně homeomorfní sféře, tudíž nebuňkové nakreslení $K_5$ na torus by bylo ekvivalentní nakreslení tohoto grafu na sféru. Ten však není v důsledku Kuratowskiho věty rovinný. #Spor#]

Hodně vypocená zkouška založená především na vymýšlení řešení k různým problémům, obtížností možná srovnatelná se zkouškami u MJe. Po dvou hodinách dřiny přišla kýžená výborná známka.

Kombinatorika a grafy II Jelínek 7. 2. 2013