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

Každý neuvedený předmět
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

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

Příspěvek od mathemage »

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.
Carpe Diem!
mathemage
Matfyz(ák|ačka) level III
Příspěvky: 130
Registrován: 14. 1. 2011 10:03
Typ studia: Informatika Ph.D.
Kontaktovat uživatele:

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

Příspěvek od mathemage »

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
Carpe Diem!
Odpovědět

Zpět na „Ostatní“