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

<{ForumPost(poster="mathemage", timestamp=2013-02-09 20:40:53)}>
Dnes se slosováním sešly hned dvě otázky z topologické teorie grafů  
  
1) **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.]

2) **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}$  
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.  
2. 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.
<{/ForumPost}>

<{ForumPost(poster="mathemage", timestamp=2013-02-09 22:18:48)}>
Teď jsem si všiml, že příklad v online sbírce úloh KAMu pod středně obtížnými kreativními úlohami :-)  
  
[http://kam.mff.cuni.cz/~sbirka/show_category.php?c=58](http://kam.mff.cuni.cz/~sbirka/show_category.php?c=58)
<{/ForumPost}>