| |
Teorie grafů LS 2012/2013
Toto není stránka aktuálního akademického roku.
Předmět: 470-4302/01: Teorie grafů (TG)
Garant: Petr Kovář
Rozsah: 6 kreditů (2/2/0/0/2)
Akademický rok: 2012/2013
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, 2009/2010, 2010/2011 a 2011/2012 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.
- Rozklady vrcholové množiny
Dokažte, že G=(V,E) je souvislý právě tehdy, když pro libovolný rozklad vrcholové množiny V na dvě množiny U a W existuje hrana e=uw∈E taková, že u∈U a w∈W.
- 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í.
- Hustý bipartitní graf
Mějme bipartitní graf G, jehož každá partita má právě n vrcholů.
Dokažte, že pokud nejmenší stupeň vrcholů v grafu G je alespoň n/2, pak G má úplné párování.
- Strnulé grafy
Najděte strnulý kubický graf pro každé sudé n≥12.
- Rozdělení grafů K5 a K3,3
Ukažte, že každý 3-souvislý graf na alespoň šesti vrcholech, který obsahuje subdivizi (rozdělení) grafu K5, obsahuje také subdivizi grafu K3,3.
- 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?
- 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í.
- 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.
- 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.
- 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?
- Téma dle dohody
Termín odevzdání projektů je 5.5.2013.
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.
- P. Kovář, Teorie grafů, učební text, (2012).
- 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.
Pro lepší pochopení vybraných pojmů můžete při studiu využít následující animace.
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 |
|
|