Teorie grafů     LS 2023/2024

Předmět: 470-4302: Teorie grafů   (TG)
Garant: Petr Kovář
Rozsah: 6 kreditů (2/2/0/0/2)
Akademický rok: 2023/2024

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, 2020/2021, 2021/2022 a 2022/2023 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.

Témata projektů pro LS akademického roku 2023/2024 se teprve připravují.

1. 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 b) 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.
2. 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?
3. 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.
4. 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_k)=2. Pro jednoznačnost uvažte například takový postup, že pro obarvení vrcholu v_i použije algoritmus vždy barvu s nejmenším dostupným indexem.
5. 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.
6. 4-pravidelné grafy   Dokažte nebo vyvraťte: Každý 4-pravidelný graf, který má úplné párování, je třídy 1.
7. Téma dle dohody

Témata, která jsou už zadaná, jsou šedá. Očekává se, že projekty budou vypracovány na úrovni, která odpovídá studentům magisterského nebo doktorského studia. Nezapomeňte na správné citace použitých zdrojů. Případná různá obtížnost témat bude kompenzována mírou, jak přísně budou projekty hodnoceny.

Termín odevzdání projektů je pondělí 6.5.2024 (pro studenty posledního ročníku v zápočtovém týdnu).

 

Zkouška   (80 bodů)

Termíny zkoušek najdete ke konci semestru v systému Edison. Zkouška má část písemnou (řešení příkladů dle zadání) a část ústní (rozprava nad probíranými tématy).

 

Literatura

• P. Kovář, Teorie grafů, učební text, (2024).
• pdf pro tisk: text základní (skriptum_teorie_grafu_tisk.pdf) a rozšířený (skriptum_teorie_grafu_rozsirene_tisk.pdf)
• pdf pro čtení na obrazovce - s aktivními linky: text základní (skriptum_teorie_grafu.pdf) a rozšířený (skriptum_teorie_grafu_rozsirene.pdf)
• pdf vhodný pro čtečky (bez okrajů): text základní (skriptum_teorie_grafu_kindle.pdf) a rozšířený (skriptum_teorie_grafu_rozsirene_kindle.pdf)
• J. Matoušek, J. Nešetřil, Kapitoly z diskrétní matematiky, Karolinum Praha (2000), ISBN 80-246-0084-6.
  Několik výtisků knihy je k dispozici v univerzitní knihovně.
• D.B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001), ISBN 0-13-014400-2.
  Několik výtisků knihy je k dispozici v univerzitní knihovně.

Je možné používat i jiné úvodní knihy a skripta, ovšem pozor: některé detaily se mohou lišit! (zejména definice pojmů) a u zkoušky platí to, co bylo probráno na přednášce.

 

Animace

Pro lepší pochopení vybraných pojmů můžete při studiu využít následující animace.

• k důkaz Cayleyho věty
• k důkazu Eulerovy věty
• ukázka konstrukce eulerova tahu
• excentricita vrcholů grafu
• k důkazu Hallovy věty
• konstrukce hyperkrychle
• hledání isomorfismu grafů
• k důkazu existence krále turnaje
• ukázky uložení struktury grafu v počítači
• k rozdílu diametrické a nejdelší v grafu
• ukázky sledu, tahu a cesty v grafu
• vztah mezi vrcholovou a hranovou souvislostí grafu

 

Konzultační hodiny

Zastihnete mne nejlépe osobně během konzultačních hodin, případně (po dohodě emailem) on-line přes MS Teams.

Best way to reach me is during my office hours. It is also possible to arrange (ahead via e-mail) an on-line appointment in MS Teams.

Den	Čas	Místnost
Čtvrtek/Thursday	9:00-10:00	EA536*
**Dne 11.4.2024 konzultace nebudou.
Konzultace on-line po předchozí domluvě.

Po předchozí domluvě jsou konzultace možné i v jinou dobu. / Or by appointment.

---

Petr<tečka>Kovar<zavináč>vsb<tečka>cz kancelář EA536, tel. 597 325 972

Upraveno: 24.04.2024