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

Základy teorie grafů B

Předmět není vypsán Nerozvrhuje se
Kód Zakončení Kredity Rozsah Jazyk výuky
01ZTGB Z,ZK 4 2+2 česky
Garant předmětu:
Přednášející:
Cvičící:
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:
Další informace:
Pro tento předmět se rozvrh nepřipravuje
Předmět je součástí následujících studijních plánů:
Platnost dat k 5. 10. 2024
Aktualizace výše uvedených informací naleznete na adrese https://bilakniha.cvut.cz/cs/predmet24524605.html