Z poslední přednášky (6-té): Probrali jsme triangulaci, duhové trojúhelníky, skorotriangulaci a problém dohratelnosti "hry" na skorotriangulaci. Pak jsme ještě měli důležitý Eulerovský graf u něhož jsme mimo jiné dokazovali že lze projít jedním tahem.

Začínáme Teorii stromů
Pro graf G=(V,E). Následující tvrzení jsou ekvivalentní:
1) G je strom.
2) G je minimální souvislý graf
3) G je maximální graf bez kružnic
4) G je "jednoznačně" souvislý graf
5) G je souvislý a |E|=|V|-1

A jen něco málo k některým bodům:
ad 1) strom si jistě všichni dovedete představit, že ? Ačkoliv musím říct, že teď právě jsem přemýšlel, že pár obrázků by neuškodilo. No třeba příště... :-((
ad 2) to minimální je myšleno tak, že pokud bych mu odendal jakoukoliv hranu již by to nebyl souvislý graf.
ad 3) no to je zase tak, že přidal-li bych jedinou hranu, již bych v grafu našel kružnici.
ad 4) ono jednoznačně znamená, že mezi každými dvěma vrcholy existuje jen jedna jediná cesta. Ty uvozovky tam pro něco jsou, jen už přesně nevím pro co :-((. Ale Vy na to přijdete.
ad 5) no k tomu snad není co dodat...

Lemma: (o listech...) - Každý strom s alespoň dvěma vrcholy má alespoň dva listy. List je vrchol stupně 1.
Důkaz: No to je doufám naprosto jasné. Prostě strom nemá kružnice, takže musí mít začátek a konec, tedy dva vrcholy ze kterých jde pouze jedna cesta... ba dokonce mnoho stromů bude mít zcela jistě mnohem více listů než-li jen dva, ale dva zcela jistě.
Důkaz z přednášky, tedy důkaz více matematický: Nechť v₀, e₁, ..., e_n, v_n je cesta T maximální délky. Potom v₀ a v_n jsou listy. Kdyby ne, pak by to nebyla nejdelší cesta nebo existuje kružnice.
No vidíte, to je úplně to samé co jsem říkal já.
Málem bych zapoměl... je dobré vzpomenout, že jsme v konečných grafech, tedy mají konečné množství vrcholů. Tohle lemma totiž v nekonečných neplatí...

Důkaz k první větě k Teorii Stromů:
1) Ţ 2): G je strom; Sporem, tedy budem předpokládat, že G-e je souvislý.
Nechť tedy x=v₀, e₁, ..., e_t, v_t=y je cesta P v G-e ale pak P+e obsahuje kružnici v G. Což je SPOR.
2) Ţ 1): Opět sporem. G je jen souvislý, nikoliv minimální, tedy obsahuje kružnici. Pak ale musíme konstatovat, že existují dva body které jsou spojeny dvěma cestami (to tak v kružnicích chodí). A to je SPOR.
3) Ţ 1): G nemá kružnice; G+e obsahuje kružnici pro každé e které ještě v grafu není (na před. označení nehrana) Ţ G je souvislý a bez kružnic, tedy strom. Proč ? No, kdyby byl G nesouvislý, tedy existuje rozklad na komponenty. Vezmu-li tedy hranu jež má každý z vrcholů v jiné komponentě a přídám jí do grafu G nevznikne kružnice (pouze spojím dvě komponenty, říkali jsme tomu most). Tedy G není maximální, existuje hrana kterou můžu přidat a nevznikne kružnice... a to je SPOR s předpokladem (3), tedy G musí být souvislý.
1) Ţ 3): G je bez kružnic; G+e a e={x,y} (vezmu jakékoliv e, které ještě v G není a jeho vrcholy pojmenuju x,y). Určitě existuje cesta P v G z x do y. Ale pak P+e tvoří kružnici. Tedy nemůžu nic přidat a je tedy maximální bez kružnic.
1) Ţ 4): Sporem. Nechť G není jednoznačně souvislý. Tedy existují různé cesty mezi x,y pak existuje kružnice...
4) Ţ 1): Je vlastně stejné jako předchozí... jen na druhou stranu :-))
1) Ţ 5): Na přednášce indukcí podle |V|. Mě to ale připadá jednodužší úvahou... totiž, už víme že pokud odstraníme jednu hranu, G nebude souvislý. Naopak pokud nějakou přidáme vznikne kružnice. Zároveň víme (4), tedy že je jednoznačně souvislý... vezměme si dva vrcholy grafu... je jasné, že každé dva vrcholy jsou spojeny jedinou cestou, případně dokonce jedinou hranou. Ke každé hraně tedy najdeme nějaký vrchol, s tím jistě všichni souhlasí. Víme, že je to strom, tedy podle Lemma výše platí, že má určitě dva listy... najděme tedy všechny listy a budeme je trhat a to tak dlouho dokud platí předpoklad lemma, tedy graf má alespoń dva vrcholy. No, pokud už jste to otrhali, pak víte, že s každým vrcholem který jste utrhli zmizela vždycky právě jedna hrana, nikdy ne víc, protože jste vždycky trhali jen listy, to opět všichni souhlasí nebo ne ? A zbyly nám jen dva vrcholy a mezi nimi jediná cesta... pak tedy |E| je |V|-1. Je tu ale jedna zákeřnost. Totiž jak to, že když utrhneme list máme ještě strom ?? No to je třeba opět nějak objasnit. Víme, že G je bez kružnic a pokud žádnou hranu nepřidám kružnice nevznikne. To že nějakou hranu odeberu nemůže mít negativní vliv, to je asi jasné, ne ? Tak tedy fajn. Vezměme ten strom. A utrhněme mu list. Pak nám zbývá dokázat, že to co zbylo je souvislé - a to je. Proč ? No protože list má stupeň 1, tedy to co jsem utrhl je vrchol a hrana. Pokud bych odebral pouze hranu spojující list se zbytkem grafu je jasné, že by vznikla komponenta a je lehké uvědomit si, že by jednou z oněch dvou komponent byla pouze ta hrana, která tvořila list. Tu ale odebírám také, tedy odebral jsem i onu komponentu. No a už jsme někdy dokazovali, že odebráním mostu vznikne vždy maximálně o komponentu víc, tedy pokud předtím byl graf souvislý, tedy měl jednu komponentu tak pak vznikly dvě a pak jsem jednu odstranil. Tedy už zase jen jedna... tedy graf je souvislý.
Jen takový malý detail. Koukám na důkaz z přednášky a zjišťuji, že je to jednuduše napsané to samé... takže vlastně žádná novinka... škoda :-).
5) Ţ 1): No, myslím, že s předchozím sáhodlouhým výkladem tohle bude hračka ne ?? Tak to zkuste sami.

Problém kostry a problém minimální kostry (MST)
Máme graf G=(V,E) který je souvislý. A máme zobrazení W: E ® R⁺ které slouží jako ohodnocení hran grafu. (G,W) nazveme vážený graf.

Kostra grafu je libovolný strom tvaru (V,E') kde E' Í E.

Pozorování: kostra existuje pro každá souvislý graf.
Proč ? Stačí vzít minimální souvislý graf a podle té dlouhé předchozí věty je to jistě strom.

Problém !? Pro daný vážený graf (G,W) nalezněte kostru (V,E') tak, aby součet ohodnocení použitých hran byl co nejnižší.
Řešení: použít Hladový Algoritmus.

Hladový Algoritmus
Máme G=(V,E) souvislý a W:E ® R⁺.
Postup je následující:
1) Seřaď hrany do neklesající posloupnosti e₁,...,e_n tak aby W(e₁) Ł W(e₂) Ł ... Ł W(e_n). Tedy je to nutné, klidně to přečíslujte podle své libosti, tak aby platilo výše napsané.
2) Definujte množiny hran E₀, E₁,..., E_n předpisem
E₀=0;
Pro E_i definujeme E_i+1 jako E_i Č {e_i+1} v případě, že taková množina neobsahuje kružnici.
Pokud by tím kružnice vznikla, žádnou hranu do E_i nepřidávej a jako E_i+1 dej množinu E_i.
3) (V,E_n) je minimální kostra.

Důkaz správnosti Hladového algortimu tedy, že nalezne minimální kostru, tedy že nalezne minimální souvislý graf s minimálním součtem ohodnocení jím použitých hran.
Možná nejprve úvaha zda je to vůbec kostra, tedy je-li to strom. No víme, že G byl souvislý a potřebujeme vědět, jestli i výsledek HA je souvislý. Pokud si uvědomíme, že jsme vzali všechny hrany grafu G a nevzali jsme jen ty co by tvořily kružnici, myslím že pak je vše jasné. Takový graf je souvislý, neboť předchozí byl souvislý a víme, že existuje souvislý graf bez kružnic. Pokud tedy předchozí byl souvislý a my jsme zkusili všechny hrany souvislého grafu a nevzali pouze ty co nám začali vytvářet hrany, je pak jasné, že jsme narazili právě na ten souvislý graf bez kružnic ?? No doufám, že ano :-)). Každopádně přemýšlejte, určitě to posléze jasné bude. Ještě taková malá úvaha - podle počtu hran si troufám tvrdit, že máme grafy souvislé s kružnicemi, pak grafy souvislé bez kružnic a pak grafy nesouvislé bez kružnic (pozor, podmínka bez kružnic je tady dost podstatné... nesouvislé s kružnicemi jistě nemusí mít méně hran než-li souvislé bez kružnic). Beru od maxima k minimu... Pokud tedy máme souvislý graf a bereme všechny jeho hrany můžeme mít souvislý graf s kružnicemi nebo bez nich. Pokud ale beru postupně všechny hrany a nezařadím jen ty které vytvoří kružnici, pak je takový graf již jen souvislý bez kružnic a dokonce má přesný počet hran, jak jsme dokazovali ve věte na začátku přednášky a to |V|-1. No ale teď už je to skutečně jasném, tedy myslím že by mělo být.
Ale teď k samému HA. Jde nám o to tedy dokázat, že součet ohodnocení použitých hran je nejnižší.
No tenhle důkaz zcela zřejmě není triviální. Zklamu Vás. Nebudu ho sem psát... jen drobná úvaha nad tím vším...
Vemte si jak jsme tu kostru sestavovali... vzali jsme tu hranu s nejnižším ohodnocením a šli jsme dál... a dál a brali jsme vždy jen ty hrany které nám netvořili kružnice, tedy mezi těmi dvěma vrcholy co měla spojovat ona cesta kterou jsme tam občas nedali existuje cesta, která už ve výsledku je. A myslím že tady je malinko kámen úrazu. Taková cesta co existuje totiž nemusí mít součet ohodnocení menší než-li ohodnocení cesty kterou do výsledku nedáme. To ale právě nevadí, protože cesta která existuje a jejíž součet počítáme zcela jistě nespojuje pouze dva vrcholy jako hrana jež jsme vyřadili. Taková cesta jich zcela jistě spojuje více a protože jsme postupovali od hran s nejnižším ohodnocením je průměr na hranu v takové cestě zcela jistě nejnižší. Představte si, že tam nějakou z vyloučených hran dáme. Vznikne kružnice, dobře to teď nevadí, zkusíme ji malinko analyzovat. Vemme jen tu kružnici. Mezi jednotlivými vrcholy jsou hrany. Pokud budeme postupně tuhle kružnici rozpojovat odstraněním vždy jedné hrany, vznikne nám vždy stejně dlouhá cesta (budeme tu kružnici jen rozpojovat, spočítáme co máme a zase ji spojíme a takhle dál až ji postupně rozpojíme na všech jejích hranách), máme tedy konstatní počet vrcholů a všechny vrcholy mezi sebou zůstanou vždy propojené (tedy souvislá komponenta). Snadno si uvědomíme, že taková cesta bude mít nejnižsí průměr na vrchol právě když bude mít nejnižší součet ohodnocení, protože počet vrcholů je konst. a to bude právě tehdy když z dané kružnice odstraníme tu hranu s nejvyšším ohodnocením. A protože jsem při stavbě kružnice postupovali od hran s nejnižším ohodnocením, je také zcela jasné, že to bude právě ta hrana kterou jsme tam přidali naposled (případně v nedaleké minulosti, připouštíme-li rovnost ohodnocení (tedy posloupnost je neklesající)). No skoro mi připadá že to za chvilí budeme mít dokázané.
Tedy dál. Vemme úvodní graf G. Ten může být buď s kružnicemi nebo bez nich, pokud je bez nich, pak je zcela jistě i kostrou, neboť kostra je strom a je to maximalní graf bez kružnic a minimální souvislý. Pak ale nemáme co řešit, protože musíme vzít všechny hrany a nemůžeme si vybrat. Vezměme tedy ten co má kružnice. Ten zase může být složený z více kružnice a nějakých bezkružnicových části, či jak to nazvat. Rozeberme si jej tedy. Kružnici jsme již řešili a víme, že algoritmus spojuje všechny vrcholy kružnice tak aby jejich součet jejich ohodnocení byl co nejnižší. A ty souvislé zbytky co tam někde jsou, tak s těmi stejně nic nenaděláme, co se volby jejich spojení týče, nemáme na vybranou, kružnici netvoří takže musíme vzít co máme a žádné hodnocení nemusíme řešit. No a je to...
Možná by někomu mohlo připadat podivné mluvit o průměru na vrchol, více asi odpovídá průměr na hranu. Je to pravda. Kdo si ale myslí, že je to kvůli tomu špatně, toho musím upozornit, že já vím kolik přesně hran bude mít hledaná minimální kostra a bude to |V|-1. A to pokud dobře vidím je fce. rostouci a tudíž je ve výsledku úplně jedno zda mluvím o průměru na hranu či vrchol, protože počet hran je s počtem vrcholů touhle fcí. svázán. Pak to tedy nebude stejné číslo, ale oba průměry vytvoří zcela stejné uspořádání. (To zni šíleně co ? Pokud to někomu vadí, nahraďte si průměr na vrchol průměrem na hranu a máte to vyřešené stejně tak).

Jarníkův, Borůvkův a Hladový algoritmus řeší ten samý problém.
Pokud se na ně chcete podívat, najdete je v učebnici. Mám pocit, že na přednášce jsme si je ukazovali, není na nich ale nic zvláštního, je to prakticky jen mechanická záležitost naučit se postup. Případný důkaz může být zajímavý, ale jak si tak na ně pamatuji z přednášky jde vesměs o dosti podobné věci. To věřím zvládnete případně nastudovat.

Kolik je koster ?
G=(V,(V nad 2)) což je úplný graf, tedy (|V| nad 2) je maximální počet všech hran v grafu množiny V. V={1, 2, ..., n}
t(n) označme počet koster grafu G (neplést s trojúhelníkovým číslem, jde o něco jiného...).

Věta: t(n)=n^n-2. (Cayley)

Kolik je neizomorfnich stromu s n vrcholy ?
Jistě jich nebude méně než-li t(n)/n! což je n^n-2/n! což zase můžeme přibližně napsat jako n^n-2/(nⁿ/eⁿ) a to jistě nebude menší než-li eⁿ/n³.

Důkaz věty o t(n): Vytvoříme jednoznačný kód stromu s n vrcholy jako C(T)=(a₁, ..., a_n-2). Pokud dokážeme, že je jednoznačný, pak t(n)=n^n-2 neboť a_i může vždy nabývat hodnot 1..n.
Konstrukce kódu: Za a₁ vezmi souseda listu s nejnižším číslem. Pak vem danou kostru bez uvažovaného listu a postup opakuj.
Rekonstrukce stromu: Vezmi vrchol s minimálním číslem, které se v kódu nevyskytuje a spoj jej s prvním číslem v kódu. Takto postupuj s tím, že kód budeˇš brát postupně zkrácený, tedy při druhém kroku budeš hledat nejnižší číslo, které se nevyskytuje v kódu s pominutím prvního čísla kódu použitého v prvním kroku. Po zpracování kódu spoj ty dva vrcholy, které jsi při rekonstrukci nikdy nebral jako nejmenší (nejmenší, které se ve zpracovávaném kuse kódu nevyskytly).