Osnova předmětu je v systému Edison.

Průběh semestru

Účast na cvičeních je povinná a účast na přednáškách je předpokládaná, neboť přednášky a cvičení navazují, případně se prolínají.

Průběh cvičení

Během semestru studenti odevzdají zápočtový projekt (maximálně za 20 bodů). Zápočet dostanou ti studenti, kteří za projekt získají alespoň 10 bodů.

Příklady k procvičení

Příklad k procvičení najdete v učebním textu, který je v seznamu literatury. Obsah souborů se průběžně aktualizuje.
Na zkoušku vybírám příklady vždy z učebního textu (z platné verze ke konci semestru). Pokud najdete v textu chyby, dejte mi, prosím, vědět.

Projekty   (20 bodů)

Můžete se podívat na seznam projektů z let 2007/2008, 2008/2009, 2009/2010, 2010/2011, 2011/2012, 2012/2013, 2013/2014, 2015/2016, 2016/2017, 2017/2018, 2018/2019, 2019/2020 a 2019/2020 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.

Témata projektů pro akademický rok LS 2021/2022 se teprve připravují.

1. Rozklad na hvězdy   Mějme d-pravidelný graf G. Dokažte, že graf G je možno hranově rozložit na kopie grafu K_1,d právě tehdy, když G je bipartitní graf.
2. k koster   V grafu K₄ existují dvě hranově disjunktní kostry. Mějme přirozené číslo k. Pro jaké nejmenší hodnoty n(k) existuje graf, který má k po dvou hranově disjunktních koster? a) Pro každé k najděte příklad grafu s n(k) vrcholy, který má k po dvou hranově disjunktních koster. Dále ukažte, že velikost grafu není postačující podmínka, tj. uveďte příklad grafu, který má alespoň tolik počet hran jako graf z části a), avšak neexistuje v něm k po dvou hranově disjunktních koster.
3. Lichý faktor   Mějme strom T se sudým počtem vrcholů. Ukažte, že ve stromu T existuje faktor, který má všechny vrcholy lichého stupně. Ukažte také, že tento faktor je jediný.
4. Bipartitní podgraf   Mějme libovolný graf G s e hranami. Kolik nejvíce hran může mít jeho bipartitní podgraf? Dokažte, že takový bipartitní podgraf existuje a že nemusí existovat bipartitní podgraf s větším počtem hran. Stačí asymptoticky přesný odhad.
5. Prostor cyklů   Ukažte, že množina vektorů, které odpovídají sudým podgrafům grafu G spolu s operací sčítání vektorů a násobení skalárem, tvoří vektorový prostor. Určete počet různých sudých podgrafů kompletního grafu K_n. Vrcholy rozlišujeme ohodnocením.
6. Automorfismy   Ukažte, že graf, který je hranově tranzitivní a není vrcholově tranzitivní, musí být bipartitní.
7. Automorfismy II   Pro~každé přirozené číslo n najděte graf s právě n automorfismy. Podaří se vám najít takové grafy, které mají současně n vrcholů? Pro která n ne?
8. Karty   Mějme balíček hracích karet, ve kterém jsou karty h různých hodnot každá v b různých barvách. Karty rozložíme na stůl do b řad, každá s h sloupci. Ukažte, že je možno v každém sloupci vybrat jednu kartu tak, že máme karty všech h hodnot. K řešení využijte párování v grafu.
9. Maximální a největší párování   Mějme k-pravidelný graf G s n vrcholy a nějaké jeho maximální párování M. Kolik nejméně může mít maximální párování grafu G hran? Tj. kolik nejvýše může v grafu G být M-nesaturovaných vrcholů? Najdete příklad takového grafu a jeho maximální párování pro k=2 a k=3?
10. 3-pravidelný graf   Dokažte, že 3-pravidelný graf G má 1-pravidelný faktor právě tehdy, když lze graf G (hranově) rozložit na cesty P₄.
11. Hladové barvení   Ukažte, že pro každý graf existuje takové seřazení vrcholů do posloupnosti, že hladový algoritmus popsaný v Lemmatu 8.5. ve skriptech dá dobré vrcholové barvení grafu G.
12. Hladové barvení II   Každý netriviální strom T je bipartitní, a proto χ(T)=2. Ukažte, že pro každé přirozené číslo k existuje takový strom T_k s nejvyšším stupněm k a takové seřazení jeho vrcholů π = v₁, v₂, ..., v_n, že algoritmus popsaný v Lemmatu 8.5., který bude obarvovat vrcholy v pořadí π, použije k+1 barev, třebaže χ(T)=2.
13. Kuratowského podgrafy   Ukažte, že každý 3-souvislý graf s alespoň šesti vrcholy, který obsahuje rozdělení grafu K₅, obsahuje také rozdělení grafu K_3,3.
14. Výhonky   Ukažte, že hra popsaná ve Cvičení 9.3.14. má pro n počátečních puntíků vždy alespoň 2n tahů.
15. Téma dle dohody