(posts visible to all students)
Martin Koutecký — 2021-11-30 11:10 (401 days ago) — reply
## 8. cvičení ### Orientované eulerovské tahy Asi nejlepší je podívat se do [skript](https://iuuk.mff.cuni.cz/~rakdver/dm/lesson9.pdf) Též [zde](https://matematika.reseneulohy.cz/3631/orientovane-eulerovske-grafy) ### Rozklad na kružnice Vzpomeňme si na důkaz věty o jednotažkách -- dokázali jsme, že v eulerovském grafu vždy dokážeme najít kružnici a když ji odebereme, tak o výsledném grafu stále platí předpoklad, že je eulerovský a proto v něm můžeme najít další kružnici atd. (též to jde říct indukcí). Též [zde](https://matematika.reseneulohy.cz/3626/eulerovsky-graf-a-sjednoceni-kruznic) ### Cracking kódu [Příklad 1](https://iuuk.mff.cuni.cz/~rakdver/dm/lesson9.pdf) ### Kolik tahů Pokud $k$ je počet dvojic vrcholů s lichým stupněm, tak bude potřeba $k$ tahů. Nahlédnout se to dá tak, že libovolně spáruji tyto vrcholy lichého stupně, přidám mezi ně pomocné hrany (možná tak vytvořím násobné hrany, ale to nevadí), výsledný graf je eulerovský a tedy má UET a když si vezmu ten UET jako začínající v jednom tom vrcholu lichého stupně, tak bude "přerušený" právě $k$ pomocnými hranami a tedy mezi pomocnými hranami bude $k$ segmentů, které tvoří otevřený tah a dohromady pokryjí všechny hrany. ### [Eulerovskost linegrafů](https://matematika.reseneulohy.cz/3632/sudost-line-grafu) Na stromy se podíváme příště :)