Předmět Algoritmická matematika 3 (KMI / AM3AI)
Na serveru studentino.cz naleznete nejrůznější studijní materiály: zápisky z přednášek nebo cvičení, vzorové testy, seminární práce, domácí úkoly a další z předmětu KMI / AM3AI - Algoritmická matematika 3, Přírodovědecká fakulta, Univerzita Palackého v Olomouci (UP).
Top 10 materiálů tohoto předmětu
Materiály tohoto předmětu
| Materiál | Typ | Datum | Počet stažení |
|---|
Další informace
Obsah
Definice grafu. Základní typy grafů.Způsoby reprezentací grafu. Matice incidence, matice sousednosti a vztahy mezi nimi. Reprezentace grafů v programech.Operace s grafy (sjednocení, průnik apod.). Izomorfismus grafů.Sled, tah a cesta. Souvislost neorientovaného a orientovaného grafu. Kondenzace orientovaného grafu.Algoritmy průchodu grafem do hloubky a do šířky.Nezávislé a dominující podmnožiny uzlů, klikovost grafu. Heuristické algoritmy pro tyto úlohy.Barvení grafu a chromatické číslo grafu. Algoritmy pro barvení grafu.Kostry grafu. Kruskalovy algoritmy nalezení minimální kostry.
Získané způsobilosti
2. PorozuměníVysvětli principy grafů a elementárních grafových algoritmů.
Literatura
Sedgewick, Robert. Algorithms in C++, Part 5: Graph Algorithms. Addison-Wesley, 2004. ISBN 0-201-36118-3.Valiente, Gabriel. Algorithms on Trees and Graphs. Springer, 2002. ISBN 3-540-43550-6.Demel, Jiří. Grafy a jejich aplikace. Academia, 2002. ISBN 80-200-0990-6.kol. autorů. Handbook of Graph Theory. CRC Press, 2004. ISBN 1-58488-090-2.Kučera, Luděk. Kombinatorické algoritmy. SNTL, 1989. Kolář, Josef, Olga Štěpánková, Michal Chytil. Logika, algebry a grafy. SNTL, 1989. Nešetřil, Jaroslav. Teorie grafů. SNTL, 1979.
Požadavky
Zápočet: Praktická implementace probíraných algoritmů.Zkouška: Znalost základů teorie grafů. Zvládnutí algoritmů pro řešení grafových úloh.
Garant
Ing. Michal Dobeš, Ph.D.