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

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

1. Cykly v síti   Mějme graf, který je kartézským součinem dvou cest P_n a P_m. Dva hráči, červený a modrý, střídavě obarvují hrany grafu G. Ten, kdo první sestaví z hran své barvy cyklus, vyhraje. Ukažte, že druhý hráč může vždy vynutit remízu.
2. Kubické grafy a párování   Ukažte, že pokud je možno kubický graf G rozložit na P₄, tak G má úplné párování.
3. Algoritmus pro triangulace trojúhelníka   Sestavte algoritmus, který vygeneruje všechny triangulace pravidelného n-úhelníka. Triangulaci můžeme pospat jako seznam úhlopříček (hran) v n-úhelníku. Dokažte, správnost algoritmu.
4. Patnáctka I   Na papír napíšeme čísla přirozená 1 až 9. Dva hráči střídavě vybírají (označují například podtržením a nadtržením) číslice, přičemž každou číslici může vybrat nejvýše jeden hráč. Ten hráč, který jako první bude moci ze svých čísel vybrat trojici čísel se součtem 15, vyhrál. Například dvě čísla 9+6 výhru nezajistí, protože jsou pouze dvě. Naproti tomu ze čtyř označených čísel 1,2,4,9 lze vybrat vítěznou trojici 2+4+9=15. Kolik existuje různých her, které končí remízou (ani jeden hráč nezíská součet 15)? Pořadí tahů rozlišujeme.
5. Patnáctka II   Na papír napíšeme čísla přirozená 1 až 9. Dva hráči střídavě vybírají (označují například podtržením a nadtržením) číslice, přičemž každou číslici může vybrat nejvýše jeden hráč. Ten hráč, který jako první bude moci ze svých čísel vybrat trojici čísel se součtem 15, vyhrál. Například dvě čísla 9+6 výhru nezajistí, protože jsou pouze dvě. Naproti tomu ze čtyř označených čísel 1,2,4,9 lze vybrat vítěznou trojici 2+4+9=15. Kolik existuje různých her, které končí vítězstvím prvního hráče? Pořadí tahů rozlišujeme.
6. Patnáctka III   Na papír napíšeme čísla přirozená 1 až 9. Dva hráči střídavě vybírají (označují například podtržením a nadtržením) číslice, přičemž každou číslici může vybrat nejvýše jeden hráč. Ten hráč, který jako první bude moci ze svých čísel vybrat trojici čísel se součtem 15, vyhrál. Například dvě čísla 9+6 výhru nezajistí, protože jsou pouze dvě. Naproti tomu ze čtyř označených čísel 1,2,4,9 lze vybrat vítěznou trojici 2+4+9=15. Existuje vítězná strategie pro některého hráče?
7. * Přemosti to! III   Pravidla hry "Přemosti to!" najdete v textu přednášek na  konci 3. kapitoly. Ukažte, že první hráč ve hře Bridge-it má vítěznou strategii.
8. Téma dle dohody

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

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, (2011).
• 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