Základy teorie grafů B
Kód | Zakončení | Kredity | Rozsah | Jazyk výuky |
---|---|---|---|---|
01ZTGB | Z,ZK | 4 | 2+2 | česky |
- Přednášející:
- Petr Ambrož (gar.)
- Cvičící:
- Petr Ambrož (gar.), František Jahoda
- Předmět zajišťuje:
- katedra matematiky
- Anotace:
-
Obsahem předmětu je výklad základů moderní teorie grafů, dopněný pohledem na některé aplikace vykládané teorie a grafové algoritmy.
- Požadavky:
- Osnova přednášek:
-
1. Základní pojmy teorie grafů.
2. Souvislost.
3. Bipartitní grafy.
4. Stromy a lesy.
5. Kostry, problém minimální kostry.
6. Eulerovy cykly a tahy, Hamiltonovy kružnice.
7. Maximální a perfektní párování.
8. Hranová barevnost.
9. Toky v sítích.
10. Vrcholová barevnost.
11. Planární grafy.
- Osnova cvičení:
-
1. Prohledávání grafu do hloubky a do šířky.
2. Nejkratší cesta v grafu (Dijkstra, A*, Floyd-Warhsall).
3. Hledání minimální kostry (Kruskalův algoritmus).
4. Hledání maximálního toku (Ford-Fulkerson).
5. Maximální párování (Edmondsův algoritmus).
6. Algoritmus planarity.
- Cíle studia:
-
Znalosti:
Pojmy z teorie grafů, jejich základní vlastnosti a vzájemné vztahy. Grafové algoritmy.
Schopnosti:
Použití uvedené teorie při modelování a řešení konkrétních otázek a úloh, včetně implementace na počítači.
- Studijní materiály:
-
Povinná literatura:
[1] J.A. Bondy, U.S.R. Murty: Graph theory. Graduate Texts in Mathematics 244. Springer, New York, (2008).
Doporučená literatura:
[2] J. Matoušek and J. Nešetřil: Kapitoly z diskrétní matematiky. MatfyzPress, 1996.
[3] Ján Plesník. Grafové algoritmy. Veda, Bratislava, (1983).
Učební pomůcky:
Počítačová učebna Windows/Unix s programovacími jazyky Python, C++.
- Poznámka:
- Rozvrh na zimní semestr 2011/2012:
- Rozvrh není připraven
- Rozvrh na letní semestr 2011/2012:
- Rozvrh není připraven
- Předmět je součástí následujících studijních plánů: