Annotation

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.

Contents

  1. Definition of a graph and basic terms.
  2. Computer representation of a graph (adjacency matrix, incident matrix, linked representation, Prüfer's number).
  3. Time and space complexity of algorithms. P and NP class, NP-hardness, NP-completeness.
  4. Graph searching, backtracking, branch and bound method.
  5. Approximation and heuristic methods. Genetic algorithms, simulated annealing, hill climbing, tabu-search, etc.
  6. Applications of path problems, shortest paths, network graphs.
  7. Eulerian trails, Hamiltonian paths and circles.
  8. Connected components, trees and spanning trees. Efficient implementations using special data structures (binary heap, disjoint sets).
  9. Steiner tree problems (network, Euclidean and rectilinear).
  10. Computational geometry and its geometric data structures (visibility graphs, Voronoi diagrams, Delaunay triangulation, convex hull). Robot motion planning.
  11. Graph colouring, cliques.
  12. Network flows (maximum flow problem, minimum cost flow problem, multicommodity flows).
  13. Graph matching.

Syllabus TG06_eng.pdf

Literature

  1. Chartrand, G. and Oellermann, O.R.: Applied Algorithmic Graph Theory. McGraw Hill, New York, 1993.
  2. Cormen, T.H., Leiserson, C.E., Rivest, R.L. and Stein, C.: Introduction to Algorithms. MIT Press, 2001.
  3. Gross, J.L. and Yellen, J.: Handbook of Graph Theory. CRC Press, Boca Raton, 2004.
  4. Gross, J.L. and Yellen, J.: Graph Theory and Its Applications. CRC Press, Boca Raton, 1998.
  5. Hochbaum, D.: Graph Algorithms and Network Flows. Lecture Notes, University of California at Berkeley, 1997, 84 pp.
  6. Michaels, J.G. and Rosen, K.H.: Applications of Discrete Mathematics. McGraw Hill, New York, 1991.
  7. Sedgewick, R.: Algorithms in Java, Part 5: Graph Algorithms. Addison Wesley, New York, 2002.