1) Kuratowskiho věta znění + důkaz
doplňující dotazy:
- implikace Rovinné grafy neobsahují dělení [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í - 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 , tvoří kružnici. [Jinak by hranice obsahovala separátor velikosti menší než tři, což je ve sporu s 3-souvislostí. Konkrétně bez vznikne 2-souvislý graf, ten se v důsledku Ušatého lemmatu dá nakreslit s kružnicovými hranicemi stěn.]
- Ekvivalence s jako zakázanými minory - tj. verse z přednášky zahrnující i Wagnerovu větu [implikace bez minoru bez dělení, páč dělení je speciální případ minoru + implikace rovinný bez minoru, neb rovinné jsou uzavřené na minory.]
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
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 . Obdobně pravý dolní roh napojen přes s levý horním.
2. nakreslení: To samé s tím rozdílem, že hrana spojující oba horní rohy je vedena přes .
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í 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í na torus? [Z předchozího bodu: takové nakreslení by musel mít 5-cyklus "vedoucí vodorovně" skrz okraj v polygonu a nesměl by mít hrany vedoucí přes hrany . 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í na torus by bylo ekvivalentní nakreslení tohoto grafu na sféru. Ten však není v důsledku Kuratowskiho věty rovinný. #Spor#]