======128GA10 -- Graphs and their Applications======
|Weekly load     |  2+0  | |Credits    |  4  |
|Semester    |  W  | |Assessment  |  ZK  |
Description: \\
Fundamentals of graph theory. Emphasis is laid on basic onsepts, applications and algorithms. From the contents: connectivity, strong conectivity, trees, shortest paths, Eulerian and Hamiltonian paths, colorings, independent sets, planar graphs.

Contents: \\
1. Basic notions (graphs, vertices, edges, degrees, paths, cycles, etc.). \\
2. Applications of path problems. \\
3. Searching algorithms (labeling, breath first search, depth first search). \\
4. Notions based on undirected paths (connected components, trees, minimal spanning trees). \\
5. Notions based on directed paths (strongly connected components, topological sorting, rooted trees, transitive closure). \\
6. Shortest path. \\
7. Problems related to shortest paths. \\
8. Flows in networks. \\
9. Application of network flow problems. \\
10. Matchings, Assignment problem. \\
11. Eulerian graphs, Chinese postman problem. \\
12. Hamiltonian paths and cycles. Travelling salesman problem. \\
13. Colorings, independent sets and cliques. \\
14. Planar graphs.  \\
 \\
Recommended literature: \\
Diestel, R.: Graph Theory, Springer, 1996, \\
Swamy, M., N., S., Thulasiraman, K., Graphs, Networks and Algorithms. New York, John Wiley&Sons, Inc., 1981. \\
Demel, J.: Graphs and their Applications, (internal material). \\
 \\
Keywords: \\
Directed graph, non-directed graph, graph model. \\
    

Teacher: Doc. RNDr. Demel Jiří CSc.