Z poslední přednášky (5-té): Zadefinovali jsme si graf, kružnici, souvislý graf, cestu, tah, sled, strom a propočítali jsme "Trojúhelníkové číslo t(n)". A nějaké další úvahy nad grafy...

Princip sudosti - pro každý graf G je počet lichých stupňů sudý.
Je to pouze připomenutí z minulé přednášky, tam již tato věta zazněla. Důkaz je zřejmý, vyplývá ze součtu stupňů grafu přes všechny vrcholy grafu, který je roven sudému číslu (2|E|), tedy pak lichých stupňů musí být sudě.
Ještě detail - nezapoměňte, že nula je sudé číslo !!

Triangulace: je množina bodů v rovině a useček a lomených čar je spojujících (body spojujících...) tak, že každá stěna tohoto nakreslení je omezena třemi body a jejich spojnicemi.

Věta: (Spernerovo lemma o duhových trojúhelnících) Nechť X je množina vrcholů v rovině spolu s nějakou triangulací. Potom počet duhových stěn triangulace je sudý.
Duhová stěna je ta stěna jejíž žádné dva vrcholy nejsou ve stejné třídě rozkladu. Tj. pokud vytvoříme rozklad všech vrcholů do nějakých tříd rozkladu, tedy do nějakých podmnožin množiny vrcholů, pak duhová stěna bude ta, jejiž každý vrchol bude v jiné podmnožině vzniklých při rozkladu.
Důkaz: Takže nyní již lépe (ještě před chvíli jsem jej měl trochu špatně, naštěstí jsem ale dostal návod). Tedy nahraďme každou stěnu triangulace vrcholem grafu a vrcholy mezi sebou propojme hranou jestliže byly od sebe dané stěny odděleny úsečkou (či lomenou čarou) jejiž jeden bod patřil do první třídy rozkladu a druhý do druhé (či opačně, každopádně však zapomeňte na chvíli na třetí třidu rozkladu (máme tam definované tři třídy rozkladu, kvůli duhovým trojúhelníkům).
Potom vrchol který je stupně jedna byl jistě duhový trojúhelník (no tady byl problém, ale už jsem to pochopil, takže proč ? - protože představte si trojúhelník. Jestliže byl duhový pak měl jeden bod v jedničce, druhý ve dvojce a třetí ve trojce (ve třídách rozkladu). A my jsme vzali ten trojúhelník a nahradili tu hranici stěny co byla v jedničce a dvojce hranou k druhému vrcholu (představující jinou stěnu). Jestliže jsme ale nevytvořili žádnou další hranu s dlaším vrcholem, musel být třetí vrchol skutečně ve trojce, protože pak tak byly hranici 2-3 a 1-3 které jsme ničím nenahrazovali).
Vrchol který je stupně dva nemůže být duhový, protože ten měl dvě stěny 1-2, tedy musel mít buď dva doby ve dvojce či dva body v jedničce. No a vrchol se stupněm tři nenajdeme, není to dost dobře možné, což je asi jasné, stačí si nakreslit nějaký trojúhelník a dát mu nějakou třídu rozkladu a pak si tam nakreslit ty vzniklé hrany. Trojku prostě nevygenerujete.
No a jsme u jádra problému. Máme graf, jehož vrcholy mají stupně 0,1,2 a jedničce odpovídá duhový trojúhelník. Pak duhových trojúhelníků musí být sudý počet, neboť tu máme princip sudosti tedy, že počet lichých stupňů grafu je sudý.

Skoro triangulace má všechny stěny trojúhelníky, pouze vnější stěnu má čtverec.

Věta: Hra na skoro triangulaci nemůže skončit remízou
Důkaz: SPOREM. Předpokládejme, že nějaká hra dopadla remízou. Můžeme předpokládat, že všechny vrcholy náleží buď jednomu nebo druhému hráči.
Definujeme tedy rozklad na X₁ X₂ X₃ kde X₁ bude množina všech bodů x pro něž existuje cesta pro prvního hráče z a (to je jeden z rohů vnějšího čtverce skoro triangulace, ten co v něm první hráč začíná) do x.
Množina X₂ je to samé ale pro druhého hráče a z bodu b tedy z obdoby bodu a ale nyní pro druhého hráče.
A množina X₃ je to, co zbývá, tedy body neobsažené v předchozích množinách rozkladu.
Uvažme nyní vnitřní stěnu S této skoro triangulace a ptáme se zda může být S duhová stěna.
A odpověď zní, že nikoliv, neboť pokud si představíme trojúhelník, kde jeden z vrcholů patří prvnímu hráči (tj. je v množině X₁, druhý z vrcholů patří druhému hráči a třetí nenáleží nikomu, pak něco není v pořádku. Někdo by si přece takový bod vzal, tj. musí patřit do jedné z prvních množin neboť k němu vede nějaká cesta buď od prvního z hráčů, či od druhého, ale vede. To že k němu ta cesta vede je jasné, ne ? Mám-li takový trojúhelník pak je tento neobsazený bod spojen jak s bodem prvního hráče tak s bodem druhého hráče nějakou hranicí mezi stěnami. Tj. cesta tam tedy určitě vede.
No a spojím-li nyní body b a d obloukem, vznikne právě jeden duhový trojúhelník (konkrétně a,b,d neboť a patří jistě prvnímu hráči, b patří jistě druhému hráči a d jistě nikomu, neboť hra skončila remízou, tedy druhý hráč se do d nemohl dostat (kdyby se dostal, vyhrál by). No a to je SPOR, neboť se přece tvrdí, že duhových trojúhelníků je sudý počet.

Mimochodem, víte co je hra ? Máte nějakou takovou "mapu" a snažíte se obsazováním jednotlivých vrcholů vytvořit cestu z jednoho Vašeho rohu do druhého, zatímco váš protihráč se snaží o to samé, jen z jiných rohů (vždy protilehlých).

Definice: G=(V,E) nazvu Eulerovský graf, jestliže má všechny stupně sudé.

Definice: Hranu nazvu most v grafu G=(V,E) jestliže graf G-e = (V,E-{e}) má více komponent než graf G.
Všichni víte co je komponenta ? To je jako jednotlivá součást grafu, tj. samostatný graf který se zbytkem grafu není nijak spojen, tj. žádnou hranou. Je to v učebnici na straně tuším 103 a dost úzce to souvisý se souvislostí grafu.

Pozorování: G má k komponent, tak G-e má nejvýše k+1 komponent.

Věta: Eulerovský graf nemá most.
Důkaz: SPOREM. Opět se principem sudosti, tedy přesněji s definicí Eulerovského grafu, neboť oddělením e, tj. mostu, nám vzniknou nějaké komponenty. Pokud vezmem bod x, který je bodem v jedné této komponentě a je to zrovna ten bod k němuž byl předtím připojen most e, pak jestliže je tento graf Eulerovský, pak měl všechny stupně sudé (z definice Eulerovskéo grafu), jestliže jsme ale odstranili z bodu x most e, pak stupeň vrcholu x musí být lichý. A to je SPOR.

Důsledek: Graf G je Eulerovský Ű existují kružnice E₁, ..., E_t (zadané pomocí množin hran) tak, že
1) sjednocení všech těchto množin E_i je právě množina E
2) E_i jsou disjunktní Důkaz: No dokazovali jsme to indukcí podle |E|. Ale když nad tím chvíli budete přemýšlet, musí to být úplně jasné :-)). Když se nad tím zamyslíte, je jasné, že aby nevzniklo více komponent, pak při zrušení jedné cesty (nějaké té e) musí existovat jiná cesta která tytéž komponenty spojuje, protože pokud ne, vzniklo by víc komponent a e by byl most. A pokud tedy existuje jiná cesta a pak jsou tam ty cesty mezi komponenty jistě dvě, protože je tam ta jiná a zároveň ještě e. No a máme kružnici... jsou dvě cesty z jedné komponenty do druhé, tedy půjdu-li po první cestě do druhé komponenty, tam přejdu do bodu odkud vychází druhá cesta zpátky a vrátím se do první komponenty a tam zase do bodu odkud vycházela první cesta, prošel jsem kružnici. A zcela jistě to můžu, neboť komponenty jsou souvislé, dostanu se tedy z jakéhokoliv jejich bodu do všech ostatních stejné komponenty.
A jen poznámka na závěr: to co nazývám komponentami ve skutečně ještě komponenty nejsou, dokud mezi nimi existuje cesta, pak to nejsou komponenty :-(, berte to tedy jenom jako název pro nějakou část grafu, o které uvažuji jako o komponentě jen z toho důvodu, že se snažím dokázat neexistenci mostu. (Pokud by e byl most a já ho odstranil, pak můžu zcela jistě mluvit o komponentách grafu, tak se snažte mi to prominout :-)).

Důsledek: Souvislý graf G=(V,E) je Eulerovský Ű když obsahuje uzavřený tah délky |E| (tj. G lze nakreslit jedním tahem - pozor, nikoliv cestou !!! U tahu dovolujeme křížit vrcholy, pouze musíme pokaždé použít jiné cesty... u cesty bychom vrholy křížit nemohli).
Důkaz: Indukcí podle |E|. Ani to sem psát nebudu, je to takové klasické. Jen pro ty co byli na přednášce - tohle je takový ten důkaz kde jsme použili "speciální patvar" jménem Zobecněný MickeyMouse. Ono je to poměrně jasné. Pokud jsou tam kružnice a jejich průnik je disjunktní, pak můžu zcela jistě procestovat (udělat tah, nikoliv cestu... pardon :-)) každou tu kružnici a když začnu v nějakém tom bodě co má společný s další kružnicí, pak jistě můžu procestovat i tu další apod...

A na závěr námět ke zkoumání (možná dostanete i Nobelovku, kdo ví...). Máme graf G=(V,E) souvislý a bez mostu. Uvažme graf G' který vytvoříme zdvojením každé hrany grafu G (komu se to takhle nelíbí, tak ať si nakreslí na každou tu druhou hranu ještě bodík, ať má dobrý pocit, že před ním je graf.
G' má všechny stupně sudé. Je vlastně obsažen ze samých kružnic. A otázka je, zda existuje rozklad na kružnice z nichž žádná není právě ta zdvojená ??