Teorie grafů
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ů:
-
- Informatika (doktorská) (povinně volitelný předmět)
- Informatika (povinně volitelný předmět)