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

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
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-DML), Algoritmy a grafy 1 (BI-AG1), Algoritmy a grafy 2 (BI-AG2), Automaty a gramatiky (BI-AAG), Výhodou jsou znalosti z předmětů Grafy a kombinatorika (NI-GAK) a Teorie složitosti (NI-CPX).

Osnova přednášek:

1. Havlova věta, DFS strom, 2-souvislost a její charakterizace, algoritmus hledání mostů, algoritmus hledání silně souvislých komponent.

2. Toky v sítích, Fordův-Fulkersonův algoritmus, k-souvislost, Fordova-Fulkersonova věta, Mengerova věta,

3. hledání párování v bipartitních grafech, Hallova věta a její důsledky, párování v obecných grafech.

4. Rovinné grafy, nakreslení grafu, Eulerova formule a její důsledky, Kuratowského věta a další otázky rovinnosti, duál nakreslení rovinného grafu, multigrafy, kreslení na obecné plochy.

5. Barvení grafů, first-fit algoritmus, věta o pěti barvách, barvení grafů na obecných plochách, Mycielskiho konstrukce, perfektní a chordální grafy, listové barvení a vybíravost, hranová barevnost.

6. Hledání vzdáleností mezi všemi dvojicemi vrcholů, Floyd-Warshallův algoritmus, využití Dijkstrova algoritmu, Fibonacciho haldy, (a,b)-stromy, B-stromy, univerzální hešování.

7. Eulerovské grafy, prostor eulerovských podgrafů grafu, hamiltonovské grafy, problém obchodní cestující, aproximační algoritmy.

8. Geometrické algoritmy, konvexní obálka, sweepline.

9. Lineární algebra v kombinatorice, počty koster.

10. Ramseyova teorie, úvod do pravděpodobnostní metody, extremální kombinatorika.

11. Algoritmy pro speciální třidy grafů, minory a jejich algoritmické využití

12. Cestové a stromové rozklady a základní vlastnosti, Dynamické programování na stromových rozkladech

MSOL, Courcellova věta, stromová šířka rovinných grafů a algoritmy pro rovinné grafy, bidimensionalita

13. 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. Skripta BI-AG2 a NI-GAK.

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

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

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

5. 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 2024/2025:
Rozvrh není připraven
Rozvrh na letní semestr 2024/2025:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 13. 2. 2025
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet1602206.html