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

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

1. Grafy s velkým obvodem   Ukažte, že pokud má rovinný graf obvod alespoň 6, tak obsahuje vrchol stupně 2. Platí tvrzení i pro~nerovinné grafy?
2. Petersenův graf   Ukažte, že Petersenův graf je silně regulární. Dokažte, že obvod Petersenova grafu je 5. Jaký je obvod doplňku Peteresnova grafu?
3. K₅ a K_3,3   Ukažte, že každý 3-souvislý graf na alespoň šesti vrcholech, který obsahuje subdivizi (rozdělení) grafu K₅, obsahuje také subdivizi grafu K_3,3.
4. Remíza v AZ-kvízu   Ukažte, že ve hře AZ-kvíz nemůže nastat remíza.
   Návod: Využijte Spernerovo Lemma.
5. Duální rovinné grafy   Pro která přirozená čísla n existuje takový jednoduchý rovinný graf G s n vrcholy, že jeho duální graf G^* je isomorfní s grafem G?
6. Červený a modrý   Obarvíme hrany kompletního grafu K₉ červenou a modrou barvou. Ukažte, že v tomto grafu existuje buď červený cyklus C₄, nebo modrý cyklus C₃.
7. Kubické grafy   Ukažte, že v kubickém grafu G bez mostů patří každá hrana do nějakého úplného párování grafu G.
8. Strnulé grafy   Najděte strnulý kubický graf pro každé sudé n≥12.
9. Bridges   Ve hře Bridges se staví mosty tak, aby z každého vrcholu vycházel vyznačený počet mostů, dva vrcholy byly spojeny nejvýše dvěma mosty a žádné dva mosty se nekřížily. Sestavte alespoň tři (netriviální) nutné podmínky, které musí vrcholy a stupně hracího plánu splňovat, aby existovalo řešení. Ukažte, že tyto podmínky nejsou postačující tak, že najdete příklad hracího plánu, který je splňuje a pro který neexistuje řešení.
10. Barvení grafů s úplným párováním   Najděte nekonečnou třídu grafů třídy 1 takových, že žádný graf G z této třídy, ve kterém nejsou při žádném jeho dobrém Δ(G)-barvení obarveny hrany nějakého úplného párování stejnou barvou. Tj. žádná jeho barevná třída nemůže být úplným párováním, aniž by se použilo více než Δ(G) barev. Ukažte, že grafy mají požadované vlastnosti. Pokud takový graf neexistuje, dokažte to.
11. Petersenův graf II   Ukažte, že Petersenův graf je vrcholově tranzitivní a že grupa automorfismů Petersenova grafu má 120 prvků. Jaká je struktura této grupy? Vysvětlete. Kolik automorfismů má doplněk Petersenova grafu?
12. Téma dle dohody

Termín odevzdání projektů je 3.5.2016.

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, (2016).
• pdf pro tisk: text základní (skriptum_teorie_grafu_tisk.pdf) a rozšířený (skriptum_teorie_grafu_rozsirene_tisk.pdf)
• pdf 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. Fronček, Úvod do teorie grafů, Slezská univerzita Opava, (1999), ISBN 80-7248-044-8.
• 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