#
Graphs and Algorithms

## Course Outline and Roass Document

Last update = Jan 4/2018.

**Topics to be covered**

- Graph Isomorphism
- basics of permutation groups
- how to write a graph isomorphism program
- graph homomorphisms
- possible research topics

- Graph Connectivity
- vertex connectivity
- edge connectivity
- basic theory
- 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

- Max Flow
- the max-flow-min-cut theorem
- the Ford-Fulkerson algorithm
- a more advanced algorithm -- eg, Karzanov's algorithm

- 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

- Hamilton cycles
- basic theory
- the crossover algorithm
- NP-completeness of HamCycle

- Graph Planarity
- Euler's formula, duals
- Kuratowski's theorem
- algorithms for testing planarity
- the bridge algorithm
- the Hopcroft-Tarjan algorithm

- 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

- Digraphs
- the depth-first search in digraphs
- strong components
- topological order
- solving 2-SAT

- tournaments
- 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.

Each student is expected to give a 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.

As this is a joint graduate/undergraduate course (7750/4060),

the assignments for the graduate and undergraduate students will be slightly different.

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.