Graphs & Algorithms

Instructors

Prof. Dr. Angelika Steger, Dr. Martin Marciniszyn

Assistants

Dr. Fabian Kuhn, Nicla Bernasconi

Time and Place

Thursday, 08.00 - 10.00 a.m., CAB G 61 (Lecture) and 10.00 - 11.00 a.m., CAB G 61 and CAB H 56 (Exercises)

Exam

Thursday, 28th June, 08.00 - 11.00 a.m., HG E5

You may use your lecture notes. This includes: printouts of all information provided during class (slides, exercises and solutions) and all handwritten notes that you may have.

Topics

Graphs are an important concept in mathematics and computer science. This lecture presents algorithms for fundamental problems in graph theory. Amongst others, it covers the following topics:

• Trees
• Connectivity
• Matchings
• Hamilton cycles
• Planar graphs
• Coloring
• Extremal graph theory

More recent problems in algorithmic graph theory will be presented in "Graphs & Algorithms: Advanced Topics" in WS 07/08.

Participants

Students of Computer Science or Mathematics in the 6th semester or later. This lecture and the follow-up lecture "Graphs & Algorithms: Advanced Topics" replace and unify the previous courses on "Graph Theory" and "Graphenalgorithmen". The presented material is the same except for some minor changes.

Material

• Lecture 2: Bridg-it, Cayley's Formula, and DFS (PDF)
• Lecture 3: Connectivity, Menger's Theorem (PDF)
• Lecture 4: Menger's Theorem (Part II) (PDF)
• Lecture 5: Min-Max Relations and Matchings (PDF)
• Lecture 6: Weighted bipartite matchings and TSP (PDF)
• Lecture 7: Planar Graphs: Euler's Formula and Coloring (PDF)
• Lecture 8: Planar Graphs: Coloring and Drawing (PDF)

Exercises

• Assignment 1: Trees
• Assignment 2: Cayley's Formula and block decomposition
• Assignment 3: Menger's Theorem
• Assignment 4: Matchings in bipartite graphs
• Assignment 5: Matchings and Min-Max Duality
• Assignment 6: Hamiltonian cycles and TSP
• Assignment 7: Planar Graphs
• Assignment 8: Planar Graphs II
• Assignment 9: Coloring I
• Assignment 10:Coloring II
• Assignment 11: Edge Coloring
• Assignment 12: Vertex Coloring and Edge Coloring

Literature

• D. B. West: Introduction to Graph Theory, Prentice Hall, 2001
• R. Diestel: Graph Theory, Springer-Verlag, 2005
• T. Cormen, C. Leiserson, R. Rivest: Introduction to Algorithms, MIT Press, 1990
• B. Bollobas: Modern Graph Theory, Springer Verlag, 1998
• The Stony Brook Algorithm Repository: A shortened version of Skiena's Algorithm Design Manual. Covers many important algorithms with downloadable implementations.