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

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

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ří získají alespoň 10 bodů.

Příklady k procvičení

Příklad k procvičení najdete v učebním textu, který najdete 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 a 2017/2018 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.

1. Periferie grafu I   Periferie grafu G je podgraf grafu G indukovaný na vrcholech s největší excentricitou. Ne každý graf může být periferií nějakého grafu. Najděte nekonečnou třídu souvislých grafů, které jsou periferií nějakého grafu. Dokažte, že výsledné grafy mají požadované vlastnosti.
2. Kostry K_n-e   Podle Cayleyho vzorce víme, že počet různých koster kompletního grafu K_n je n^n-2. Určete počet různých koster (rozlišujeme vrcholy grafu) kompletního grafu bez jedné pevně zvolené hrany e.
3. Go na šachovnici   Dva hráči střídavě rozmisťují kameny hry GO na šachová políčka. Jeden hráč umisťuje bílé kameny a druhý černé, na každé políčko přijde právě jeden káme. Vyhraje ten hráč, který ze svých kamenů jako první sestaví čtverec 2×2kameny ve své barvě. Ukažte, že druhý hráč má neprohrávající strategii. Nápověda: užijte párování v grafu.
4. 2-souvislé grafy   Dokažte, že graf G je 2-souvislý právě tehdy, když pro každou trojici vrcholů x, y, z ∈ V(G) existuje (x,z)-cesta přes vrchol y.
5. Perfektní párování I   Perfektní 1-faktorizace kubického grafu G je taková trojice úplných párování M₁, M₂, M₃ grafu G, že párování jsou po dvou disjunktní a sjednocení kterýchkoliv dvou párování tvoří hamiltonovský cyklus grafu G. Ukažte, že trojboký hranol C₃ x K₂ má perfektní 1-faktorizaci. Ukažte, že tato 1-faktorizace je určena jednoznačně.
6. Perfektní párování II   Perfektní 1-faktorizace kubického grafu G je taková trojice úplných párování M₁, M₂, M₃ grafu G, že párování jsou po dvou disjunktní a sjednocení kterýchkoliv dvou párování tvoří hamiltonovský cyklus grafu G. Ukažte, že hranol C_n x K₂ nemá perfektní 1-faktorizaci pro žádné n>3.
7. Téma dle dohody

Termín odevzdání projektů je pondělí 6.5.2019.

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.

Literatura

• P. Kovář, Teorie grafů, učební text, (2019).
• 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.
• D.B. West, Introduction to graph theory - 2nd ed., Prentice-Hall, Upper Saddle River NJ, (2001), ISBN 0-13-014400-2.

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