Graphs AND Algorithms PDF

Instructors

Prof. Dr. Angelika Steger, Dr. Martin Marciniszyn

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 

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.