Graph Theory
Lecturer: John Quinn
Teaching takes place Tues 1800-2100, Faculty of Science building S008.
(Gnucleus peer network; human neuron connections; Tokyo subway map)
This course will make students familiar with useful techniques in graph theory and show what the applications of these techniques are. Supporting material will be added to this page each week.
The main reference for this course is the online textbook Graph Theory with Applications by Bondy and Murty. Lecture notes are available below, but they only contain an overview of the classes—attendance is essential.
Week 1: Introduction
- What is graph theory useful for?
- Examples of graphs—directed, undirected, acyclic, complete, bipartite.
- Incidence and adjacency.
- Example application: shortest path problem.
- Example application: three houses problem.
- Example application: matching jobs to applicants.
- Useful glossary page (Wikipedia).
- Lecture notes
Week 2: Trees
- Application: planning an efficient road network.
- Definition of trees.
- Properties of trees: number of edges and vertices, degree of vertices, cut edges.
- Spanning trees.
- Kruskal's algorithm.
- Lecture notes
Week 3: Connectivity
- Cayley's formula.
- Cut vertices, vertex cuts, edge cuts.
- Blocks; the block detection algorithm challenge.
- Connectivity and edge-connectivity.
- Application: designing resilient computer networks.
- Lecture notes
Week 4: Euler tours and Chinese postmen
- The seven bridges of Königsberg
- Conditions for Eulerian graphs
- The Chinese postman problem
- Fleury's algorithm
- Hamilton paths
- Lecture notes
Week 5: Matchings and coverings
- Matches, perfect matches, matches in bipartite graphs
- Personnel assigment problem
- Hall's theorem
- The marriage theorem
- The Gale-Shapley algorithm
- Lecture notes
Week 7: Directed graphs
- Orientations of an undirected graph
- Tournaments
- Euler tours in digraphs
- Application: rotational position sensor
- Into to graphical models
- Lecture notes
(no class week 8.)
Week 9: Message passing
- Message passing rules for counting vertices
- Separability
- Counting paths through a grid
- Viterbi (min-cut) algorithm
- Lecture notes
Week 10: Probabilistic graphical models
- Dependence/conditional dependence/conditional independence
- Observed and latent variables
- Marginalisation and inference
- Lecture notes
Week 13: Network flow
- Flow/resultant flow
- Network cuts
- Max-flow min-cut
- The Ford-Fulkerson algorithm
- Lecture notes
Page maintained by John Quinn