Zk 15. 6. 2009, Kratochvíl

Základní kurs oboru oboru informatika, ve kterém jsou uceleně probrány základní partie teorie grafů a množinových systémů jak po strukturální, tak po algoritmické stránce.
Uživatelský avatar
hkvm
Matfyz(ák|ačka) level II
Příspěvky: 50
Registrován: 3. 6. 2008 20:45
Typ studia: Informatika Mgr.
Kontaktovat uživatele:

Zk 15. 6. 2009, Kratochvíl

Příspěvek od hkvm »

1. Kolik koster má graf:
Obrázek

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; a1, ..., ak)
je graf s vrcholy V = {0, ..., n-1}
a hranami E = {uv | u ∈ V, v ∈ {(u+a1) mod n-1, (u+a2) mod n-1, ..., (u+ak) mod n-1} }
Příklad: C(8; 3, 4)
Obrázek
a) Dokaž, ze pro grafy C(4k; a1, ..., ak), k >= 1, kde 0 < a1 < a2 < ... < ak < 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í K2,3 ani K4.

Příklady 1-4 za 6 bodů, 5-6 za 8
1 >= 30
2 >= 18 ?
3 >= nepamatuju
Naposledy upravil(a) hkvm dne 16. 6. 2009 13:43, celkem upraveno 1 x.
Šlupka
Matfyz(ák|ačka) level I
Příspěvky: 39
Registrován: 7. 11. 2007 22:12
Typ studia: Informatika Bc.

Re: Zk 15. 6. 2009, Kratochvíl

Příspěvek od Šlupka »

Jen oprava hodnocení

1 >= 30
2 >= 22
3 >= 18
Odpovědět

Zpět na „DMI011 Kombinatorika a grafy I“