Teorie grafů
Kód předmětu: 128TG |
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 (NG201900GM), skupina Geodézie a kartografie, spec. Geomatika, PV předměty, 1. semestr (NH20180001_1), dop. semestr 1 (tento studijní plán platil do akademického roku 2021/22 ) - 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 ) - studijní plán Geodézie a kartografie, specializace Geomatika (NG2023GMP), skupina Geodézie a kartografie, spec. Geomatika, PV předměty, 1. semestr (NH20180001_1), dop. semestr 1 (přechod na nový studijní plán, platí pro nástup 2021 a 2022 ) |