Předmět Grafy v inženýrství (N445044A)

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 N445044A - Grafy v inženýrství, Fakulta chemicko-inženýrská, Vysoká škola chemicko-technologická v Praze (VŠCHT).

Materiál	Typ	Datum	Počet stažení

Sylabus

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. Acyklické očíslování, topologické uspořádání grafu, test acykličnosti grafu.4. Prohledávání grafů a šířky a hloubky, vzájemná dosažitelnost uzlů a její analýza.5. Výstupní zobrazení soustavy rovnic, párování v bipartitních grafech - přiřazovací problémy, souvislost s výstupním zobrazením soustavy rovnic.6. Silné komponenty souvislosti, komponenty 2-souvislosti - ireducibilní subsystémy soustavy rovnic, záložní provoz a analýza kritických prvků sítě.7. Kondenzace a hierarchická struktura grafu, splňování preferencí - optimální posloupnost výpočtů.8. Nakreslení grafu do roviny - aplikace při návrhu tištěných spojů a integrovaných obvodů.9. Hledání nejkratší cesty v grafu.10. Kostra grafu - nalezení nezávislých obvodů, minimalizace potrubní sítě.11. Toky v sítích, eulerovský tah.12. Síťové grafy, maximální párování v obecném grafu - metoda kritické cesty.13. Lokální a systematické prohledávání, programování s omezujícími podmínkami - hledání optimálních cest, diskrétní optimalizace, principy řešení, metoda větví a mezí.14. Příklady technických a inženýrských aplikací teorie grafů.

Literatura

Z: Demel J.: Grafy a jejich aplikace. Academia, Praha, 2002. ISBN 80-200-0990-6.Z: Matoušek J., Nešetřil J.: Kapitoly z Diskrétní matematiky. Matfyzpress, Praha, 1996. ISBN 80-85863-17-0.D: Töpfer P.: Algoritmy a programovací techniky. Prometheus, Praha, 1995. ISBN 80-85849-83-6.D: Kučera L.: Kombinatorické algoritmy. SNTL, Praha, 1983.

Garant

Cejnar Pavel RNDr.