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

Průběh přednášek

Výuka na začátku semestru bude probíhat on-line. Nad dalším průběhem semestru visí otazník. Pokud nebude otevřená škola pro studenty, budou přednášky on-line přes MS Teams. Ideálně budou probíhat přednášky a cvičení jednou týdně.

Plán pro samostudium v době uzavření školy

Naplánujte si předem studium během týdne. Doporučuji například dodržovat schéma podobné školnímu rozvrhu. Věnujte se Teorii grafů alespoň 2× týdně: ve středu přečíst a pochopit novou látku ze skript včetně důkazů. Vypracovat čtvrtinu (nejlehčích) cvičení. Ve čtvrtek si text znovu přečtěte a vyřešte zbývající cvičení. Během cvičení se zeptejte, pokud si nebudete vědět rady s řešením nějakého příkladu.
Špatný dotaz: nevím, jak vyřešit příklad X.Y.
Správný dotaz: zkoušel jsem využít větu V, zkoušel jsem podobný postup jako v důkazu D/ve cvičení C, ale nevím jak využít vlastnost W.

Průběh přednášek a cvičení

Během semestru se studenti budu účastnit on-line hodin a budou každý týden vypracovávat samostatné úkoly. Domácí úkoly budou bodované a zápočet dostanou ti studenti, kteří získají alespoň 20 bodů.

Domácí úkoly (20 bodů)

Každý týden dostanete zadány příklady k procvičení, které vypracujete a odevzdáte do stanoveného termínu. Zadání najdete ve skriptech, která jsou ke stažení v seznamu literatury. Obsah souborů se průběžně aktualizuje.

Týden 8.-12.2.2021

Kapitola 1.

• Nastudovat věty a definice v sekci 1.1. a 1.2. včetně jejich důkazů.
• Vyřešit Cvičení 1.1.4. a 1.2.18.
• Přečíst sekce 1.3. a 1.4., nastudovat definice.
• Vyřešit Cvičení 1.3.7. a 1.4.1.

Dotazy a vyřešené úkoly posílejte do středy dalšího týdne emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Týden 15.-19.2.2021

Kapitola 2.

• Nastudovat lemmata a definice v sekci 2.1. a 2.2. včetně jejich důkazů.
• Vyřešit Cvičení 2.1.4., 2.2.4. a 2.2.10.
• Nastudovat definice a věty v sekci 2.3.
• Vyřešit Cvičení 2.3.4. a 2.3.10.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 22.-26.2.2021

Kapitola 3.

• Nastudovat definice, lemmata a věty v sekci 3.1 včetně jejich důkazů.
• Vyřešit Cvičení 3.1.5., 3.1.10. a 3.1.17.
• Nastudovat definice a věty v sekci 3.2. a 3.3.
• Vyřešit Cvičení 3.3.2., 3.3.6.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 1.-5.3.2021

Kapitola 4.

• Nastudovat definice a věty v sekci 4.1 včetně jejich důkazů.
• Vyřešit Cvičení 4.1.5. a 4.1.7.
• Nastudovat definice v sekci 4.2.
• Vyřešit Cvičení 4.2.1., 4.2.7. a 4.2.9.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 8.-12.3.2021

Kapitola 5.

• Nastudovat definice a věty v sekci 5.1 včetně jejich důkazů.
• Vyřešit Cvičení 5.1.2. a 5.1.11
• Nastudovat Věty v sekci 5.2. a jejich důkazy, určitě důkazy Vět 5.5 a 5.6. (důkaz Mengerových vět ani Lemmatu 5.10 netřeba). Vypracujte Cvičení 5.2.11., 5.2.12. a 5.2.13. (pozor, cvičení jsou ve skriptech přečíslována)
• Určitě doporučuji pečlivé přečtení Chybné použití indukce (z rozšiřujících témat) a oba řešené Příklady 1 a 2.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 15.-19.3.2021

Kapitola 6.

• V tomto týdnu si projděte sekci 6.1., definici párování v grafu, definice rozšiřujících a alternujících cest v grafu. Nastudujte Větu 6.1. včetně důkazu. Myšlenka důkazu je důležitá, je konstruktivní.
• Vyřešte Cvičení 6.1.3. a 6.1.6.
• Nastudujte kapitolu 6.2. Pojem okolí a ryzí okolí vrcholů je snadný, pečlivě si rozmyslete, jak vypadá okolí množiny vrcholů v bipartitním grafu.
• Nastudujte si Hallovu větu i její důsledek, tvrzení bude později vícekrát využito.
• Vypracujte Cvičení 6.2.6.
• Projděte kapitolu 6.3. a dobře si rozmyslete rozdíl mezi párováním a pokrytím. Tvrzení Königovy věty je důležité, důkaz však zkoušet nebudu.
• Vypracujte Cvičení 6.3.1.
• Nastudujte Tutteovu Větu včetně důkazu, důležitá je myšlenka obou implikací a Důledek (Druhá Petersenova věta).
• Cvičení 6.4.3. není třeba vypracovávat.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 22.-26.3.2021

Kapitola 7.

• V tomto týdnu si projděte sekci 7.1., definici hranového barvení a barevných tříd grafu. Důkaz Vizingovy Věty 7.1. nemusíte číst, avšak její Důsledek 7.2. nastudujte včetně důkazu.
• Vyřešte Cvičení 7.1.3. a 7.1.7.
• Nastudujte kapitolu 7.2.
• Vypracujte Cvičení 7.2.2. a 7.2.3.
• Nastudujte kapitolu 7.3., zejména definici rozkladu grafu.
• Vypracujte Cvičení 7.3.4.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 29.3.-2.4.2021

Kapitola 8.

• V tomto týdnu si projděte sekci 8.1., definice i věty včetně důkazů.
• Vyřešte Cvičení 8.1.1. a 8.1.11.
• Nastudujte kapitolu 8.2. včetně důkazy Brooksovy věty.
• Vypracujte Cvičení 8.2.3.
• Nastudujte kapitolu 8.3., důkazy tvrzení nebudu zkoušet.
• Vypracujte Cvičení 8.3.1. a 8.3.4.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 6.-9.4.2021

Kapitola 9.

• Projděte kapitolu 9.1., důležité je rozlišovat rovinné a planární grafy.
• Vypracujte Cvičení 9.1.6.
• Nastudujte kapitolu 9.2. Důležité je správně chápat pojem rozdělení grafu - libovolný počet hran můžeme nahradit cestami, planaritu to neovlivní.
• Vypracujte Cvičení 9.2.2. a 9.2.6.
• Nastudujte začátek kapitoly 9.3. včetně důkazů. Myšlenky z důkazů budou využity ve cvičeních.
• Vypracujte Cvičení 9.3.5. Postupujte analogicky jako v důkazech vět. Vypracujte také Cvičení 9.3.10.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 12.-16.4.2021

Kapitola 9.

• Dokončíme téma kapitoly 9.3. včetně důkazů.
• Vypracujte Cvičení 9.3.7. a 9.3.20.
• Projděte kapitolu 9.4., důležitý je pojem duálního grafu.
• Vypracujte Cvičení 9.4.1., 9.4.8. a 9.4.20.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 19.-23.4.2021

Kapitola 10:

• Nastudujte kapitolu 10.1. a rozmyslete si, proč je průsečíkové číslo určeno jednoznačně.
• Vypracujete snadná Cvičení 10.1.3. a 10.1.6.
• Pročtěte kapitolu 10.2. a 10.3.
• Vypracujete snadná Cvičení 10.3.2., 10.3.6. a 10.3.9.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 26.-30.4.2021

Kapitola 11:

• Nastudujte kapitolu 11.1. včetně uvedených důkazů tvrzení.
• Vypracujete Cvičení 11.1.8., 11.1.11 a 11.1.15.
• Pročtěte kapitolu 11.2.
• Vypracujete Cvičení 11.2.14. a 11.2.26.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 3.-7.5.2020

Kapitola 12:

• Nastudujte kapitolu 12.1.
• Vypracujete Cvičení 12.1.3., 12.1.4. a 12.1.8.
• Nastudujte kapitolu 12.2. Dobře si rozmyslete rozdíl mezi slabě souvislým, jednostranně souvislým a silně souvislým digrafem.
• Vypracujete Cvičení 12.2.6. a 12.2.13.
• Nastudujte kapitolu 12.3. Důležité jsou myšlenky v důkazu vět 12.7. a 12.8. Pozornost věnujte i pojmu král turnaje.
• Jako nepovinné zkuste vyřešit Cvičení 12.3.4. a 12.3.18. (poslední domácí úkol)

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz. Vyřešené úkoly vložte do středy do LMS.

Týden 10.-14.5.2020

Zápočtový týden, žádný domácí úkol.

Kapitola 12:

• Dokončíme kapitolu 12.3. Důležité jsou myšlenky v důkazu vět 12.9. a 12.12.

Projekty   (10 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 a 2019/2020 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.

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. 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₄.
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)=2.
5. Cykly v Petersenově grafu   Ukažte, že v Petersenově grafu neexistuje cyklus délky 7. Pro které délky d existuje v Petersenově grafu cyklus délky d?
6. 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.
7. Rozklad na cesty P₃   Dokažte nebo vyvraťte: cesta P₃ rozkládá netriviální souvislý graf G právě tehdy, když G má sudý počet hran.
8. 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í 3.5.2021. Budou akceptovány projekty odevzdané do 10.5., avšak po 6.5. už nebude čas upozorňovat na chyby v projektu pře jeho bodováním.

Zkouška   (70 bodů)

Termíny zkoušek najdete v systému Edison. Zkoušky probíhají on-line přes MS Teams. 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, (2020).
• 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