Students will acquire the basic concepts of graph theory. They will learn to analyze various engineering tasks and solve them using known graph algorithms. They will then learn how to

recognize computationally hard tasks and gain insight into many of the problems solved by graph theory.

Studenti si osvojí základní pojmy teorie grafů. Naučí se analyzovat rozličné inženýrské úlohy a řešit je pomocí známých grafových algoritmů. Dále se naučí

rozpoznávat výpočetně náročné úlohy a získají přehled o mnoha problémech řešitelných pomocí teorie grafů.

A: Matousek J., Nesetril J.: Invitation to Discrete Mathematics, Oxford University Press, USA, 2011. ISBN 978-0198570424

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: Turzík, Pavlíková: Diskrétní matematika, skripta, VŠCHT Praha, 2007, ISBN:978-80-7080-667-8

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: Diestel R.: Graph Theory (Graduate Texts in Mathematics). Springer, 2010. ISBN 978-3642142789. (anglicky)

www.vscht.cz/mat/Ang/indexAng.html

www.vscht.cz/mat/

lectures, tutorials, individual work on the project

přednášky, konzultace, samostatná práce na projektu

1. Basic concepts in graph theory. Representations of graphs.

2. Paths in graphs. The task of the shortest path.

3. Connected graphs, Components od connectivity, blocks of graphs.

4. Trees. Heap-sort.

5. Spanning tree. Greedy algorithm for minimal spanning tree.

6. System of distinct representatives. Matching in bipartite graphs.

7. Matching in general graphs.

8. Euler graphs. The Chinese postman problem.

9. Hamiltonian graphs. The travelling salesman problem.

10. Planar graphs and their characteristics.

11. Coloring. Coloring of Planar graphs.

12. Flows in networks.

13. Theory of complexity. P and NP problems. Good characteristics.

14. Examples of graph theory applications.

1. Základní pojmy teorie grafů. Reprezentace grafů.

2. Cesty v grafech. Úloha nejkratší cesty.

3. Souvislost grafu, komponenty souvislosti, 2-souvislé grafy.

4. Stromy. Rychlé třídění.

5. Kostra grafu. Hladový algoritmus pro hledání minimální kostry.

6. Systém různých reprezentantů. Párování v bipartitních grafech.

7. Párování v obecných grafech.

8. Eulerovské grafy. Problém čínského pošťáka.

9. Hamiltonovské grafy. Problém obchodního cestujícího.

10. Rovinné grafy a jejich charakteristika.

11. Barevnost. Barevnost rovinných grafů.

12. Toky v sítích.

13. Teorie složitosti. Problémy třídy P a NP. Dobrá charakteristika.

14. Příklady aplikací teorie grafů.

none

nejsou

The subject is finished by an oral exam. Before the exam is completed, 3 of the tasks assigned during the semester must be successfully solved.

Předmět je zakončen ústní zkouškou, před jejím absolvováním je třeba úspěšně vyřešit 3 z úloh zadaných v průběhu semestru.