Studenti budou umět:

• Analyzovat průmyslovou úlohu pohledem teorie grafů a abstrahovat řešený problém

• Řešit danou úlohu pomocí známých efektivních grafových algoritmů a dále budou mít přehled o mnoha problémech řešitelných pomocí různých grafových algoritmů

• Rozlišovat výpočetně náročně řešitelné úlohy

Students will be able to:

• Extract the graph theory problems in industrial tasks.

• Analyze the graph theory problems and solve them using efficient known graph algorithms.

• Have an overview of many problems solvable by various graph algorithms.

• Distinguish computationally intensive tasks among various graph theory problems.

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.

R: Thulasiraman K., Swamy M. N. S.: Graphs: Theory and Algorithms. Wiley-Interscience, 1992. ISBN

978-0471513568.

R: West D. B.: Introduction to Graph Theory. Pearson, 2001. ISBN 978-0130144003.

A: Diestel R.: Graph Theory (Graduate Texts in Mathematics). Springer, 2010. ISBN 978-3642142789.

A: Christofides N.: Graph Theory. An Algoritmic Approach. Academic Press Inc, 1975. ISBN 978-0121743505.

Přednášky a cvičení.

Lectures and courses.

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ů.

1. Graphs, their terminology and basic definitions, graph description and coding

2. Time and storage complexity of algorithms, NP-complete problems

3. Directed and undirected acyclic graphs, topological ordering and finding a circle in a graph

4. Depth-first and breadth-first search in graphs, mutual reachability of nodes and its analysis

5. Bipartite graphs, matching in bipartite graphs and output mapping of equation set

6. Strong components, k-edge-connected graphs and irreducible subsystems of equation set

7. Graph condensation, hierarchical structure of a directed graph, computation sequencing

8. Planar graphs, their embedding into a plane, application in design of printed circuits and chips

9. Finding shortest path in graphs

10. Pipeline networks, spanning tree, search for independent circuits, minimization of pipe networks

11. Flow networks, maximum flow and minimum cut, transportation reserves, Eulerian path

12. General matching problems, critical path method

13. Discrete optimization, local and systematic search - principles of methods, constraint programming, branch-and-bound method

14. Examples of application in engineering and technology

• elektronické materiály k předmětu dostupné na http://moodle.vscht.cz/course/view.php?id=117

• Ondřej Čepek: Přednášky na MFF UK z předmětů Algoritmy a datové struktury I, Složitost I.

• electronic materials available at http://moodle.vscht.cz/course/view.php?id=117 (in Czech language)

• Matematika I

• alespoň jeden předmět o programování v libovolném programovacím jazyku

• Mathematics I or any equivalent subject

• one subject in the topic of computer programming (in any computer language)