| Název předmětu: | Grafy v inženýrství | |||||||
| Ústav: | 445 - Ústav počítačové a řídicí techniky | |||||||
| Přednášející: | Ing. Vladimír Hanta, CSc | |||||||
| Zástupce: | Ing. Filip Michálek | |||||||
| Typ předmětu: | povinně volitelný | |||||||
| Rozsah / zakončení: | 2/1 kz | |||||||
| Kredity | 3 | |||||||
| Doporučený ročník / semestr: | 1/1 | |||||||
| Povinné předcházející předměty: | ||||||||
| Doporučené předcházející předměty: | ||||||||
| Souhrn: | ||||||||
| Předmět je úvodem do teorie grafů s důrazem na inženýrské aplikace grafových algoritmů. Přehledně a na příkladech zavádí základní pojmy a vlastnosti, zabývá se metodami číselného kódování grafů. Formuluje praktické grafové problémy z reálného života (rozsáhlé soustavy rovnic, numerické aplikace, inženýrské problémy, operační výzkum a rozhodovací problémy apod.) a uvádí základní efektivní algoritmy jejich řešení. Stručně se zabývá i problematikou výpočetní složitosti algoritmů, NP- úplnými problémy a principy jejich přibližného řešení. | ||||||||
| Anotace: | ||||||||
| 1 | Grafy, terminologie a základní definice, popis a kódování grafů | |||||||
| 2 | Výpočetní a paměťová složitost algoritmů, NP-úplné problémy | |||||||
| 3 | Prohledávání grafů a šířky a hloubky, backtracking, výstupní zobrazení soustavy rovnic | |||||||
| 4 | Transformace soustavy rovnic na graf, vzájemná dosažitelnost uzlů a její analýza | |||||||
| 5 | Silně souvislé komponenty, ireducibilní subsystémy soustavy rovnic | |||||||
| 6 | Kondenzace grafu, hierarchická struktura grafu. Optimální posloupnost výpočtů | |||||||
| 7 | Potrubní sítě, kostra grafu, nalezení nezávislých obvodů, minimalizace potrubní sítě | |||||||
| 8 | Mnohovrstvový rozhodovací proces, hledání optimálních cest | |||||||
| 9 | Síťové grafy, metoda kritické cesty | |||||||
| 10 | Párování v bipartitních grafech, souvislost s výstupním zobrazením soustavy rovnic | |||||||
| 11 | Diskrétní optimalizace, principy řešení, metoda větví a mezí | |||||||
| 12 | Hamiltonovské cesty, plánování a rozvrhování procesů | |||||||
| 13 | Rovinné grafy, jejich rovinné rozkreslení | |||||||
| 14 | Příklady technických a inženýrských aplikací teorie grafů | |||||||
| Literatura: | ||||||||
| [1] | Demel J.: Grafy a jejich aplikace. Academia, Praha, 2002 | |||||||
| [2] | Kučera L.: Kombinatorické algoritmy. SNTL, Praha, 1983 | |||||||
| [3] | Kolář J., Štěpánková O., Chytil M.: Logika, algebry a grafy. SNTL, Praha 1989 | |||||||