| |
Teorie grafů LS 2010/2011
Toto není stránka aktuálního akademického roku.
Předmět: 457-305/2: Teorie grafů (TG)
Garant: Petr Kovář
Rozsah: 6 kreditů (2/2/0/0/2)
Akademický rok: 2010/2011
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ří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.
Můžete se podívat na seznam projektů z let 2007/2008, 2008/2009 a 2009/2010 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.
- Cykly v síti
Mějme graf, který je kartézským součinem dvou cest Pn a Pm.
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.
- Kubické grafy a párování
Ukažte, že pokud je možno kubický graf G rozložit na P4, tak G má úplné párování.
- 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.
- Stromolezec I
Máme dán kořenový strom T a v kořenu je jediná figurka.
Dva hráči střídavě pohybují figurkou, přičemž jsou povoleny pouze tahy směrem od kořene k listům, tahy zpět nejsou povoleny.
Hrač, který nemůže udělat tah, prohrál.
Ukažte, že hra nemůže skončit remízou.
Má některý hráč vítěznou strategii?
Najděte nutnou a dostatečnou podmínku, kterou musí splňovat stom T, aby první hráč vyhrál bez ohledu na volbu v každém svém tahu.
- Stromolezec II
Máme dán kořenový strom T a v kořenu je jediná figurka.
Dva hráči střídavě pohybují figurkou, přičemž jsou povoleny pouze tahy směrem od kořene k listům, tahy zpět nejsou povoleny.
Hrač, který nemůže udělat tah, prohrál.
Ukažte, že hra nemůže skončit remízou.
Má některý hráč vítěznou strategii?
Najděte nutnou a dostatečnou podmínku, kterou musí splňovat stom T, aby první hráč měl vítěznou strategii.
- 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.
- 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?
- * 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.
Termín odevzdání projektů je 9.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.
Můžete se podívat na seznam projektů z let 2007/2008, 2008/2009 a 2009/2010 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.
- P. Kovář, Teorie grafů, učební text, (2011).
- 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.
Toto není stránka aktuálního akademického roku.
Konzultační hodiny
Zastihnete mne nejlépe osobně během konzultačních hodin, případně (po dohodě emailem) on-line přes MS Teams.
Best way to reach me is during my office hours. It is also possible to arrange (ahead via e-mail) an on-line appointment in MS Teams.
Den | Čas | Místnost |
Čtvrtek/Thursday | 9:00-10:00 | EA536* |
**Dne 11.4.2024 konzultace nebudou. |
Konzultace on-line po předchozí domluvě. |
Po předchozí domluvě jsou konzultace možné i v jinou dobu. / Or by appointment.
|
Petr<tečka>Kovar<zavináč>vsb<tečka>cz kancelář EA536, tel. 597 325 972 |
Upraveno: 22.03.2016 |
|
|