Zk 15. 6. 2009, Kratochvíl

1. Kolik koster má graf:
   http://img44.imageshack.us/img44/9048/kostry.png

2. Najdi max. tok v síti a dokaž že nemůže být větší
   (To bylo lehké že tu síť ani nebudu kreslit: ze přímo zdroje vycházelo jen 8+8 a bylo snadné najít tok velikosti 16)

3. Vytvořující funkci pro: (1, 3, 5, 9, ...)

4. Cyklant C(n; a₁, ..., a_k)
   je graf s vrcholy V = {0, ..., n-1}
   a hranami E = {uv | u ∈ V, v ∈ {(u+a₁) mod n-1, (u+a₂) mod n-1, ..., (u+a_k) mod n-1} }
   Příklad: C(8; 3, 4)
   http://img361.imageshack.us/img361/5374/cykl.png
   a) Dokaž, ze pro grafy C(4k; a₁, ..., a_k), k >= 1, kde 0 < a₁ < a₂ < ... < a_k < 2k platí, že pro ně existuje perfektní párování.
   b) Má každý takovýto graf (z áčka) Hamiltonovskou kružnici?

5. a) Dokaž: Každý vrcholově 2-souvislý graf na více než 4 vrcholech obsahuje hranu, jejíž kontrakcí se neporuší 2-souvislost
   b) Je pravda, že v nich můžu kontrahovat libovolnou hranu bez porušení 2-souv.?

6. Vnějškově rovinný graf je takový, který se dá nakreslit tak, že má všechny vrcholy na vnější stěně. Dokaž, že vnějškově rovinné jsou právě grafy, které neobsahují dělení K_2,3 ani K₄.

Příklady 1-4 za 6 bodů, 5-6 za 8
1 >= 30
2 >= 18 ?
3 >= nepamatuju

Jen oprava hodnocení

1 >= 30
2 >= 22
3 >= 18