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

Teorie grafů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
11Y1TG KZ 2 2P+0C česky
Přednášející:
Lucie Kárná
Cvičící:
Lucie Kárná
Předmět zajišťuje:
ústav aplikované matematiky
Anotace:

Základní grafové pojmy, formalizace popisu grafů, způsoby reprezentace grafu. Úlohy teorie grafů, instance, zadání. Prohledávání grafu, minimální kostra grafu, stromy, nejkratší dráha, Eulerovské tahy, párování v bipartitních grafech, toky v sítích, cirkulace, kritická cesta, úloha obchodního cestujícího. Algoritmy řešení existenčních a optimalizačních úloh. Výpočetní složitost, přístup k řešení NP-těžkých úloh, heuristické postupy.

Požadavky:

znalost základních pojmů z teorie grafů

Osnova přednášek:
Osnova cvičení:
Cíle studia:

Základní teoretické poznatky o možnosti použití teorie grafů při řešení konkrétních úloh z oblasti dopravních a logistických problémů. Klasické úlohy, zaměření na dopravní sítě. Seznámení s problematikou algoritmizace.

Studijní materiály:

Demel, J: Grafy a jejich aplikace, Praha, Academia, 2002

Matoušek, J., Nešetřil, J.: Kapitoly z diskrétní matematiky, Praha, Karolinum, 2009

Poznámka:
Rozvrh na zimní semestr 2020/2021:
Rozvrh není připraven
Rozvrh na letní semestr 2020/2021:
Rozvrh není připraven
Předmět je součástí následujících studijních plánů:
Platnost dat k 25. 2. 2021
Aktualizace výše uvedených informací naleznete na adrese http://bilakniha.cvut.cz/cs/predmet24063405.html