Předmět: 457-305/2: Teorie grafů   (TG)
Garant: Petr Kovář
Rozsah: 6 kreditů (2/2/0/0/2)
Akademický rok: 2009/2010

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í

K dispozici je soubor tg_cviceni.pdf, ve kterém je celá řada příkladů k procvičení. Obsah souboru budu průběžně aktualizovat. Na zkoušku vybírám příklady vždy z tohoto textu (z platné verze ke konci semestru).
Text je prozatím spíš pracovní, některé pasáže ještě nejsou dokončené. 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 a 2008/2009 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.

1. Barvení grafu II   Dva hráči hrají následující hru. Střídavě obarvují vrcholy souvislého grafu G tak, že první hráč obarvuje modrou barvou, druhý hráč červenou barvou a každý musí vybarvit některý nevybarvený vrchol, který je sousední s vrcholem, jež jeho protihráč vybarvil v předchozím tahu. Vyhraje ten, kdo jako poslední obarví nějaký vrchol. Ukažte, že druhý hráč může vždy vyhrát, když graf G má úplně párování.
2. Jezdec na šachovnici II   Je dobře známo, že na šachovnici o rozměru 8×8 polí je možné putovat šachovým koněm tak, abychom každé poli navštívili právě jednou a vrátili se na výchozí pozici. Ukažte, že
   • žádná šachovnice o rozměru n×n polí pro n liché takové putování neumožňuje.
   • * najděte uzavřenou cestu koněm pro nekonečno mnoho hodnot n.
3. Nejmenší emulátor K₆   Podle Kuratowského Věty víme, že graf K₆ není planární. Ukažte, že existuje takový planární graf G, jehož vrcholy je možno obarvit šesti barvami (ohodnotit) 1,2,...,6 tak, že každý vrchol obarvený barvou i je sousední s vrcholy všech zbývajících pěti barev. Najděte nejmenší takový graf a ukažte, že menší neexistuje.
4. Hra "podvodní šprouti" II   Na papíře je nakresleno n výhonků, každý s r_i rameny pro . Hráči se střídají, kdo nemůže udělat další tah, prohrál. V každém tahu spojí hráč křivkou dva výhonky tak, aby neprotnul žádnou jinou křivku a na křivku nakreslí nový výhonek se dvěma rameny, jedno na každou stranu křivky. Nové křivky se připojují pouze k neobsazeným ramenům výhonků. Ukažte, že hra není spravedlivá, neboť o vítězi je dopředu rozhodnuto bez ohledu, jaké jsou tahy hráčů.
5. Přemosti to! I   Pravidla hry "Přemosti to!" najdete v textu přednášek na  konci 3. kapitoly. Ukažte, že hra Bridge-it nemůže skončit remízou.
6. Přemosti to! II   Pravidla hry "Přemosti to!" najdete v textu přednášek na  konci 3. kapitoly. Ukažte, že druhý hráč ve hře Bridge-it nemůže mít vítěznou strategii.
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. 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.
9. Předepsaný počet automorfismů   Pro každé přirozené číslo k najděte příklad grafu, který má právě k automorfismů.
10. Pravidelný graf bez úplného párování   Pro každé k>1 popište konstrukci k-pravidelného grafu, který nemá úplné párování.
11. 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í.
12. Hamiltonicita hyperkrychle   Ukažte, že hyperkrychle Q_n řádu n>2 je hamiltonovský graf.
13. Hra Pandemic Odhady maximálního/minimálního počtu hráčů pro vítěznou strategii ve hře Pandemic v závislosti na zvolených parametrech hracího plánu.
14. Téma dle dohody

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

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.
Můžete se podívat na seznam projektů z let 2007/2008 a 2008/2009 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.

Literatura

• D. Fronček, Úvod do teorie grafů, Slezská univerzita Opava, (1999), ISBN 80-7248-044-8.
• 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.