Teorie grafů

Garant předmětu:

Ondřej Suchý

Přednášející:

Ondřej Suchý, Tomáš Valla

Cvičící:

Ondřej Suchý, Tomáš Valla

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 2023/2024:

Rozvrh není připraven

Rozvrh na letní semestr 2023/2024:

Rozvrh není připraven

Předmět je součástí následujících studijních plánů:

• Informatika (doktorská) (povinně volitelný předmět)
• Informatika (povinně volitelný předmět)