| |
Teorie grafů LS 2017/2018
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: 2017/2018
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, 2011/2012, 2012/2013, 2013/2014, 2015/2016 a 2016/2017 nebo na vzorový projekt ve formátu pdf: tg_vzorovy_projekt.pdf.
- Barvení grafů s úplným párováním
Najděte nekonečnou třídu grafů třídy 1 takových, že žádný graf G z této třídy, ve kterém nejsou při žádném jeho dobrém Δ(G)-barvení obarveny hrany nějakého úplného párování stejnou barvou.
Tj. žádná jeho barevná třída nemůže být úplným párováním, aniž by se použilo více než Δ(G) barev.
Ukažte, že grafy mají požadované vlastnosti.
Pokud takový graf neexistuje, dokažte to.
- Orientace rovinného grafu
Ukažte, že každý rovinný graf je možno zorientovat tak, že nejvyšší odchozí stupeň vrcholů v grafu je nejvýše 3.
- Vrcholová a hranová souvislost pravidelných grafů
Ukažte, že v~každém 1-, 2- a 3-pravidelném grafu je vrcholová souvislost rovna hranové souvislosti.
Ukažte, že pro r-pravidelné grafy, kde r≥4, vrcholová souvislost může být odlišná od hranové souvislosti.
- Periferie grafu I
Periferie grafu G je podgraf grafu G indukovaný na vrcholech s největší excentricitou.
Ne každý graf může být periferií nějakého grafu.
Najděte nekonečnou třídu souvislých grafů, které jsou periferií nějakého grafu.
Dokažte, že výsledné grafy mají požadované vlastnosti.
- Periferie grafu II
Periferie grafu G je podgraf grafu G indukovaný na vrcholech s největší excentricitou.
Ne každý graf může být periferií nějakého grafu.
Najděte nekonečnou třídu grafů, které nemohou být periferií žádného grafu a dokažte to.
- Grafy s malým diametrem
Mějme graf G s průměrem 2, nejvyšším stupněm n-2 a alespoň čtyřmi vrcholy.
Dokažte, že graf G má alespoň 2n-4 hran.
- Chromatické číslo sjednocení grafů
Dokažte nebo vyvraťte: Mějme dva souvislé grafy G a H, potom χ(G ∪ H) ≤ χ(G) + χ(H).
- Téma dle dohody
Termín odevzdání projektů je pondělí 7.5.2018.
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, (2016).
- 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: 21.01.2019 |
|
|