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

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ů)

1. Triangulace roviny   Máme dán rovinný graf G, ve kterém je každá oblast (i vnější) ohraničena právě třemi hranami. Každý vrchol grafu G obarvíme jednou ze tří barev. Ukažte, že v grafu G existuje vždy sudý počet trojúhelníků, které mají vrcholy obarveny všemi barvami.
2. Hanojské věže   Máme tři kolíky a sadu osmi disků různých velikostí. Na začátku je všech osm disků seřazeno podle velikosti na prvním kůlu. Úkolem je přemístit všechny disky na jiný kůl za dodržení následujících podmínek:
   1. vždy se přesunuje pouze jeden disk,
   2. nikdy nesmí ležet větší disk na menším.
   Zformulujte úlohu hanojských věží pomocí teorie grafů a vyřešte ji pro věž ze tří disků. Najděte nejmenší možný počet přesunů, které jsou nutné pro přemístění celé věže.
3. Jednobarevné cesty   Hrací plán hry má tvar čtverce, ve kterém jsou dva protilehlé rohy obarveny modrou barvou a zbývající dva protilehlé rohy červenou barvou. Oblast uvnitř čtverce obsahuje několik vrcholů a hrany rozdělují vnitřní část čtverce tak, aby každá oblast byla trojúhelník. Dva hráči střídavě obarvují vrcholy uvnitř čtverce modrou a červenou barvou. Ten, který takto první sestaví jednobarevnou cestu spojující dva protilehlé rohy, vyhrál. Ukažte, že hra nemůže skončit remízou.
4. Barvení grafu   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 první hráč může vyhrát vždy, když G nemá úplné párování a druhý hráč může vždy vyhrát, když graf G má úplně párování.
5. Přelévání nádob   Na přednášce jsme ukázali, jak využít grafy při hledání řešení úloh, které souvisí s odměřením jistého množství kapaliny, pokud mám k dispozici jen několik nádob různé velikosti. Při řešení příkladu na přednášce bylo řečeno: "Hranou spojíme pouze takové dva vrcholy stavového grafu, kdy existuje legální tah oběma směry. Taková přelití, která není možné vrátit nebudeme uvažovat, protože se dá rozmyslet, že nepovedou ke kratšímu řešení." Je toto tvrzení pravdivé v obecném případě (tj. kdy máme i jiné nádoby než 8, 5 a 3 litry? Pokud ano dokažte, a pokud ne uveďte příklad.
6. Jezdec na šachovnici   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 4×n polí takové putování neumožňuje.
7. 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.
8. Hranová barvení pravidelných grafů s artikulací   Ukažte, je-li G pravidelný graf, který obsahuje artikulaci, tak chromatický index grafu G je větší než nejvyšší stupeň v grafu G.
9. Tištěný spoj   Pro jaké největší n můžete nakreslit graf K_n na oboustranný tištěný spoj? Dokažte a uveďte příklad.
10. Stereografická projekce   Dokažte užitím stereografické projekce, že kreslení grafů do roviny odpovídá kreslení grafu na sféru. Najděte předpis bijekce.
11. Téma dle dohody

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

Témata, která jsou už zadaná, jsou šedá. Očekává se, že projekty budou vypracovány na úrovni, která odpovídá studentům čtvrtého ročníku vysoké školy. 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 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.