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

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ě: v pondělí přečíst a pochopit novou látku ze skript včetně důkazů. Vypracovat čtvrtinu (nejlehčích) cvičení. Ve středu si text znovu přečtěte a vyřešte zbývající cvičení.

Týden 16.-20.3.2020

Všem studentům byly emailem rozeslány následující pokyny.

Kapitola 5:

• Vyřešit Cvičení 5.1.8. a 5.1.17
• Nastudovat Věty v sekci 5.2. a jejich důkazy, určitě důkaz Vět 5.5 a 5.6. (důkaz Mengerových vět ani Lemmatu 5.10 netřeba). Doporučuji Cvičení 5.2.5., 5.2.4. a 5.2.7.
• Určitě doporučuji pečlivé přečtení z rozšiřujících témat Chybné použití indukce oba řešené Příklady 1 a 2.

Kapitola 6.

• V tomto týdnu si ještě 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í. K procvičení pak doporučuji příklady 6.1.1. a 6.1.4.
• (Jednu variantu důkazu Cvičení 6.1.4. a Cvičení 6.1.9. plánuji udělat až bude probíhat výuka.)

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Týden 23.-27.3.2020

Všem studentům byly emailem rozeslány následující pokyny.

Kapitola 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.3. a Cvičení 6.2.7, případně 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 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).
• Vypracujte Cvičení 6.4.1. a Cvičení 6.4.3, případně Cvičení 6.4.6.
• (Důkaz Věty 6.1. a Cvičení 6.4.6. a plánuji udělat pokud bude probíhat výuka.)

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Týden 30.3.-3.4.2020

Všem studentům byly emailem rozeslány následující pokyny.

Kapitola 7:

• Nastudujte kapitolu 7.1., pojem dobrého hranového barvení grafu i barevných tříd.
• Nastudujte si Vizingovu větu a její důsledek, důkaz Vizingovy věty se neprobírá.
• Vypracujte Cvičení 7.1.1., Cvičení 7.1.3, a Cvičení 7.1.5.
• Nastudujte kapitolu 7.2. a vypracujte Cvičení 7.2.5.
• Kapitolu 7.3. si pročtěte, rozklady zkoušet nebudu, ale terminologie se využije u jiných témat.
• Doporučuji (nepovinně) vypracovat Cvičení 7.3.2

Kapitola 8:

• Začněte studovat kapitolu 8.1., pojem dobrého vrcholového barvení grafu i barevných tříd.
• Srovnejte vrcholová a hranová barvení grafů, zejména chromatický index a chromatické číslo kompletních bipartitních grafů.
• Nastudujte Větu 8.1. a 8.2. včetně důkazů, použité myšlenky se využijí při řešení příkladů později.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Týden 6.-9.4.2020

Všem studentům byly emailem rozeslány následující pokyny.

Kapitola 8:

• Pokračujte ve studiu kapitoly 8.1. Je důležité chápat, že dolní odhady chromatického čísla říkají, že chromatické číslo nemůže být menší než nějaká hodnota, ale může být libovolně velké. Naopak horní odhady chromatického čísla dávají nástroj, jak určit horní mez chromatického čísla, které však pro daný graf může být mnohem menší.
• Lemma 8.5. (a navazující Lemma 8.6.) dávají jednoduchý algoritmus, jak daný graf dobře obarvit, třebaže výsledné barvení může použít více barev, než je nutné minimum.
• Vypracujte Cvičení 8.1.2. a Cvičení 8.1.6. Horní odhad chromatického čísla se zpravidla určí obarvením, dolní odhad pak využitím nějakých vět. Jako nepovinné je Cvičení 8.1.9., podaří se vám jej vyřešit?
• Nastudujte kapitolu 8.2. včetně důkazu Brooksovy věty. Důkaz zkoušet nebudu, ale struktura důkazu postupných řešení speciálnějších a speciálnějších tří grafů je v praxi velmi často využívaná.
• Vypracujte Cvičení 8.2.2. (doporučuji pečlivé čtení textu) a Cvičení 8.2.4. (doporučuji postupovat nepřímo.)

Kapitola 9:

• Začněte studovat kapitolu 9.1., důležité je rozlišovat rovinné a planární grafy.
• Vypracujte Cvičení 9.1.4., které ukáže schopnost argumentovat pomocí definice.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Týden 14.-17.4.2020

Všem studentům byly emailem rozeslány následující pokyny.

Kapitola 9:

• 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.1. jako analogii důkazu Věty 9.2. Důležité je začít cyklem C_6. Vypracujete cvičení 9.2.7.
• Nastudujte kapitolu 9.3. včetně důkazů. Myšlenky z důkazů budou využity ve cvičeních.
• Vypracujte Cvičení 9.3.5. a nepovinně také Cvičení 9.3.8. Postupujte analogicky jako v důkazech vět.
• Nastudujte kapitolu 9.4. Všiměte si, že duální graf není určený jednoznačně a že zavedením duálního grafu nemusíme zavádět barvení oblastí rovinného grafu.
• Vypracujte Cvičení 9.4.3. a 9.4.12.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Týden 20.-24.4.2020

Všem studentům byly emailem rozeslány následující pokyny.

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.1. a 10.1.2.
• Pročtěte kapitolu 10.2. a vypracujte Cvičení 10.2.2.
• Nastudujte kapitolu 10.3. a vypracujte Cvičení 10.3.1.
• Jako nepovinné zkuste vyřešit Cvičení 10.3.4.

Dotazy posílejte emailem na adresu Petr<tečka>Kovar<zavináč>vsb<tečka>cz.

Týden 27.-30.4.2020

Kapitola 11:

• Nastudujte kapitolu 11.1. včetně důkazů. Pečlivě si rozmyslete, jaký je rozdíl mezi grafem, který je euleroský a grafem, který je možno nakreslit jedním tahem.
• Vypracujete Cvičení 11.1.1. a 11.1.8.
• Jako nepovinné zkuste vyřešit Cvičení 11.1.9.
• Nastudujte kapitolu 11.2. myšlenky z důkazu Věty 11.5. a Lemmatu 11.6 budou využity ve cvičeních. Důležité je rozumět významu Vět 11.10. a 11.13., budou využity ve cvičeních.
• Vypracujete Cvičení 11.2.4., 11.2.5. a 11.2.7.
• Kapitolu 11.3. zkoušet nebudu.

Týden 4.-7.5.2020

Kapitola 12:

• Nastudujte kapitolu 12.1. Všimněte si, že rozlišujeme stupně příchozí, odchozí a celkové a že smyčka se počítá do celkového stupně dvakrát. Vypracujte Cvičení 12.1.2.
• Nastudujte kapitolu 12.2. Dobře si rozmyslete rozdíl mezi slabě souvislým, jednostranně souvislým a silně souvislým digrafem. Vypracujte Cvičení 12.2.4.
• 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.
• Vypracujete Cvičení 12.3.5. a 12.3. 6.
• Jako nepovinné zkuste vyřešit Cvičení 12.3.17.

Týden 11.-15.5.2020

Zápočtový týden.

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 2018/2019 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.

1. 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.
2. Barvení grafu   Mějme netriviální graf G. Dokažte, že chromatické číslo grafu G je rovno klikovému číslu grafu G, jestliže doplněk grafu G je bipartitní graf.
3. Rozklad na hvědy   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.
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. Jezdec na šachovnici 4×n   Ukažte, že jezdec na šachovnici o rozměru 4×n polí nemůže projít šachovnici tak, aby na každé pole skočil právě jednou a posledním tahem se vrátil na výchozí pole. Využijte vlastnosti hamiltonovských grafů.
6. Téma dle dohody

(Prodloužený) termín odevzdání projektů je pondělí 18.5.2020.

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, (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