Vinicius Santos

Graphics Engineer at Ubisoft. Working on Assassin’s Creed Codename Red.

Warning: This page is not the official one of the current course at PUC-MG and only showcases information that is related to a past offering.

About

This course gives students a theoretical and practical introduction to graph algorithms. Basic graph theory definitions, theorems, and principles are presented to students so that they can develop a complete understanding of the most widely known graph algorithms for particular problems such as shortest paths, minimum spanning trees, maximum flow, among others. During the course, students must implement some of these algorithms and apply them into toy problems, whose specifications are mostly based on online judges such as UVa or SPOJ.

Textbooks

  • Goldbarg, M., and GoldBarg, E., “Grafos: conceitos, algoritmos e aplicações”. 2012.
  • Cormen, T. H., et al., “Introduction to Algorithms”. 3rd ed. 2009.
  • Diestel, R., “Graph Theory”. 2005.
  • Bondy, J. A., and Murty, U. S. R., “Graph Theory with Applications”. 1982.

Slides

Click on the topic name to download the respective slides as zip files. The inside content is in Portuguese because the course is offered at a brazilian university.

Topic Description
Introduction Overview on graph theory: basic definitions, trees, complete and bipartite graphs, operations on graphs, isomorphism, adjacency and incidence matrices.
Graph Search Breadth-first and depth-first search algorithms, complexity analysis, and edge labeling.
Topological Sorting Topological sort using depth-first search.
Shortest Paths Shortest path problem, optimal substructure, Bellman-Ford algorithm, and Dijkstra’s algorithm.
Connectivity Vertex and edge connectivity, connected/strongly-connected components, Kosaraju’s algorithm, cut-vertices, cut-edges, and Tarjan’s algorithm.
Eulerian/Hamiltonian Graphs Eulerian graphs and trails, Hierholzer’s algorithm, Chinese Postman Problem, Hamiltonian graphs and cycles, Traveling Salesman Problem.
Spanning Trees Minimum spanning tree problem, Prim’s algorithm, and Kruskal’s algorithm.
Flow Networks Maximum flow problem, Ford-Fulkerson method, Max-flow/Min-cut theorem, and Edmonds-Karp algorithm.
Graph Coloring Scheduling problems, vertex coloring, 2-coloring algorithm, edge coloring, face coloring, four color theorem.
Planar Graphs Planar and plane graphs, dual graphs, Euler’s formula, Kuratowski’s Theorem, and Wagner’s theorem.

Updated: