Logo ČVUT
ČESKÉ VYSOKÉ UČENÍ TECHNICKÉ V PRAZE
STUDIJNÍ PLÁNY
2019/2020

Teorie grafů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah
PI-TGR ZK 4 2P+1C
Přednášející:
Ondřej Suchý (gar.)
Cvičící:
Ondřej Suchý (gar.)
Předmět zajišťuje:
katedra teoretické informatiky
Anotace:

Studovány budou jak strukturální otázky tak otázky algoritmizace a složitosti základních optimalizačních úloh na speciálních třídách grafu. Z hlediska výpočetní složitosti bude pozornost věnována hranici mezi polynomiální řešitelností a NP-težkostí jednotlivých variant studovaných úloh.

Požadavky:

Všeobecné znalosti z diskrétní matematiky a teorie algoritmů pokryté přednáškami Základy diskrétní matematiky (BI-ZDM), Algoritmy a grafy 1 (BI-AG1), Algoritmy a grafy 2 (BI-AG2), Automaty a gramatiky (BI-AAG), případně Efektivní algoritmy (BI-EFA) a Grafové algoritmy a základy teorie složitosti (BI-GRA). Výhodou jsou znalosti z předmětů Pokročilá algoritmizace (MI-PAL) a Teorie složitosti (MI-CPX).

Osnova přednášek:

1. Toky v sítích

2. Aplikace toků - míra souvislosti grafů, Ford-Fulkersonova a Mengerova věta, Hallova věta

3. Párování v grafech

4. Rovinné grafy - Kuratowského věta, věta o 5 barvách

5. Barevnost grafů

6. Hamiltonovské grafy

7. Minory a jejich algoritmické využití

8. Dynamické programování na stromech a mřížkách, cestové a stromové rozklady a základní vlastnosti

9. Dynamické programování na stromových rozkladech

10. MSOL, Courcellova věta a alternativní charakterizace stromové šířky

11. Počítání stromové šířky, stromová šířka rovinných grafů a algoritmy pro rovinné grafy, bidimensionalita

12. Bakerové posouvací technika, rozklady hustých grafů

Osnova cvičení:
Cíle studia:

Cílem předmětu je podat přehled o moderních metodách teorie grafů.

Studijní materiály:

1. R. Diestel, Graph Theory, 5th edition, Springer, 2017.

2. T. Valla, J. Matoušek: Kombinatorika a grafy, skriptum MFF UK, 2005.

3. Marek Cygan, Fedor V. Fomin, Łukasz Kowalik, Daniel Lokshtanov, Dániel Marx, Marcin Pilipczuk, Michał Pilipczuk, Saket Saurabh, Parameterized Algorithms, Springer 2015.

4. Downey, Rodney G., Fellows, Michael R.: Fundamentals of Parameterized Complexity, Springer, 2013.

Poznámka:

Informace o předmětu a výukové materiály naleznete na https://courses.fit.cvut.cz/PI-TGR/

Další informace:
https://courses.fit.cvut.cz/PI-TGR/
Rozvrh na zimní semestr 2019/2020:
Rozvrh není připraven
Rozvrh na letní semestr 2019/2020:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 15. 9. 2019
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet1602206.html