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.

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

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

A: 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.

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.

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

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

Lectures and courses.

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

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

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

• Mathematics I or any equivalent subject

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

• Matematika I

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

To complete the course, student must successfully elaborate 5 individual tasks. The assignment of all the tasks is announced during the semester and all the tasks must be successfully finished by the specified date in the exam period.

Pro udělení klasifikovaného zápočtu je třeba úspěšně vyřešit 5 zadaných úloh. Zadání jednotlivých úloh je postupně zveřejňováno v průběhu semestru a všechny úlohy je třeba úspěšně vyřešit nejpozději k určenému datu ve zkouškovém období.