Graphs and Algorithms

1. Graph Isomorphism
   • basics of permutation groups
   • how to write a graph isomorphism program
   • graph homomorphisms
   • self-complementary graphs
   • possible research topics
2. Graph Connectivity
   • vertex connectivity
   • edge connectivity
   • basic theory
   • degree sequences, Erdos-Gallai theorem
   • the depth-first-search algorithm for cut-vertices, cut-edges
   • max-flow algorithms to find the connectivity
   • the problem of finding a simple algorithm for separating pairs
   • possible research topics
3. Max Flow
   • the max-flow-min-cut theorem
   • the Ford-Fulkerson algorithm
   • max-matching
   • a more advanced algorithm -- eg, Karzanov's algorithm
4. Graph Colouring
   • edge-colouring and max-matchings
   • Vizing's theorem and related algorithms
   • vertex-colouring
   • chromatic polynomials, how to find them
   • the 4 Colour Theorem
   • NP-completeness of colouring problems
   • exhaustive search algorithms for vertex-colouring
   • nowhere-zero flows
   • possible research topics
5. Hamilton cycles
   • basic theory
   • the crossover algorithm
   • NP-completeness of HamCycle
6. Graph Planarity
   • Euler's formula, duals
   • Kuratowski's theorem
   • algorithms for testing planarity
     • the bridge algorithm
     • the Hopcroft-Tarjan algorithm
     • the Klotz algorithm
7. Graphs on other surfaces
   • rotation systems
   • the projective plane
   • the torus
   • the Klein bottle
   • the double torus
   • an algorithm for the projective plane
   • a possible algorithm for the torus
   • a possible algorithm for the Klein bottle
   • possible research topics
8. Digraphs
   • the depth-first search in digraphs
     • strong components
     • topological order
     • solving 2-SAT
   • tournaments
   • self-converse digraphs
   • modules (intervals)

Assignments

There will be 3 assignments, each worth 10% of the final grade.
There will be an individual coding project to implement a significant algorithm.
The project will be worth 25% of the final grade. As this is a significant part
of the final grade, it is expected that the students will contribute a
correspondingly significant amount of work to it.
Each student is to give a 15-20 minute presentation on his/her project
in the last two weeks of classes.
There will be a final exam (3 hours), worth 45% of the final the grade.

This is a joint graduate/undergraduate course (7750/4060),
therefore the assignments for the graduate and undergraduate students will differ slightly.

Programming is to be done in C, C++, Java, or Python.
Please write your own classes.
Use arrays and pointers.
Do not use a "visual" programming environment.