Teorie grafů

Kód předmětu: 128TG
Garant předmětu: doc. RNDr. Jiří Demel, CSc.
Zakončení předmětu: Z,ZK
Počet kreditů: 4 kred.
Rozsah výuky: 2+2

Anotace	(semestr )
Teorie grafů - základní pojmy, formulace grafových úloh, základní algoritmy řešení se zřetelem na efektivnost výpočtu.
Obsah
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.
Literatura
*Povinná literatura*: [1] 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
Návaznosti
--
Studijní plány
Předmět je zařazen do následujících studijních plánů: - studijní plán Geodézie a kartografie, specializace Geomatika (NG2023GM), skupina Geodézie a kartografie, spec. Geomatika, PV předměty, 1. semestr (NH20230001_1), dop. semestr 1 (platí pro nástup od akad. roku 2023/24 )