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

Teorie grafů

Přihlášení do KOSu pro zápis předmětu Zobrazit rozvrh
Kód Zakončení Kredity Rozsah Jazyk výuky
128TG Z,ZK 4 2P+2C česky
Garant předmětu:
Jiří Demel
Přednášející:
Jiří Demel
Cvičící:
Jiří Demel
Předmět zajišťuje:
katedra inženýrské informatiky
Anotace:

Teorie grafů - základní pojmy, formulace grafových úloh, základní algoritmy řešení se zřetelem na efektivnost výpočtu.

Požadavky:

Nejsou

Osnova přednášek:

Základní pojmy, sled, tah, cesta,

grafové modely reálných problémů, eulerovské tahy,

algoritmy prohledávání do šířky a do hloubky,

souvislost, silná souvislost,

acyklické grafy, topologické uspořádání,

stromy a kořenové stromy,

úloha o minimální kostře,

nejkratší cesty,

toky v sítích,

párování, přiřazovací úloha,

hamiltonovské cesty a kružnice,

nazávislost, barevnost, kliky,

rovinné grafy.

Osnova cvičení:

Základní pojmy, sled, tah, cesta,

grafové modely reálných problémů, eulerovské tahy,

algoritmy prohledávání do šířky a do hloubky,

souvislost, silná souvislost,

acyklické grafy, topologické uspořádání,

stromy a kořenové stromy,

úloha o minimální kostře,

nejkratší cesty,

toky v sítích,

párování, přiřazovací úloha,

hamiltonovské cesty a kružnice,

nazávislost, barevnost, kliky,

rovinné grafy.

Cíle studia:

Schopnost používat graf jako vyjadřovací prostředek k modelování reálných situací, schopnost řešit základní grafové úlohy.

Studijní materiály:

!Demel, J.: Grafy a jejich aplikace, 2002, Academia Praha, ISBN 80-200-0990-6; 2. vydání vlastním nákladem 2015, ISBN 80-260-7684-1

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