Supervisorprof. RNDr. Ing. Miloš Šeda, Ph.D.
The course provides an introduction to graph theory and familiarises students with basic terms. It deals with the following topics: Graph representation. Time complexity of algorithms. Data structures (binary heap, disjoint sets, ...). Eulearian trails, Hamiltonian paths. Breadth-first searching, depth-first searching, backtracking, branch and bound method. Connectivity and reachability. Shortest path problems (Dijkstra's algorithm, Floyd-Warshall algorithm). Network graphs. Trees, spanning tree problem, Steiner tree problems. Fundamentals of computational geometry, Voronoi diagrams, Delaunay triangulation. Network flows. Graph colouring. Graph matching.