Module Identifier MA32410  
Academic Year 2000/2001  
Co-ordinator Dr V C Mavron  
Semester Semester 1  
Pre-Requisite MA13510 or MA13610 or equivalent  
Course delivery Lecture   19 x 1hour lectures  
  Seminars / Tutorials   3 x 1hour example classes  
Assessment Exam   2 Hours (written examination)   100%  
  Resit assessment   2 Hours (written examination)   100%  

General description
Graph theory has developed from research into a number of classical problems - Euler's Konigsberg Bridge Problem, Kirchoff's Electrical Network Problem, Cayley's Enumeration of Chemical Graphs and the Four Colour Problem for Plane Maps. A full solution is found to the Euler Problem and a related problem due to Hamilton is studied. Shortest and longest path algorithms are given with applications, for instance, to job scheduling (PERT). Algorithms are described for finding optimum weight spanning trees inweighted graphs. They can be used, for example, to find least cost connected transport networks. The theory of flows in transport networks is outlined: in paticular the max-flow-min-cut theorem. Two areas of application are traffic flows and matching theory.

To provide an introduction to some topics in classical graph theory. To describe network algorithms such as those for finding optimum length paths, optimum weight spanning trees and maximum flows and to illustrate them with applications to simple cases.

Learning outcomes
On completion of this module, students should be able to:

1. Elementary graph theory. Special graphs. Simple applications. Associated matrices. Walks and connectivity. Eulerian and Hamiltonian graphs. Trees.
2. Paths and components in graphs. Algorithms to determine components. Shortest (Dijkstra) and longest path algorithms. Floyd's algorithm.
3. Topological sorting. Critical Path Analysis.
4. Spanning trees. Prim's and Kruskal's algorithms for finding optimum weight spanning trees.
5. Transport networks. Flows, cuts. The max-flow-min-cut theorem. The Ford-Fulkerson algorithm.
6. Applications.

Reading Lists
** Recommended Text
R P Grimaldi. Discrete and Combinatorial Mathematics. Addison-Wesley
** Supplementary Text
N Biggs. Discrete Mathematics. OUP
C L Liu. Elements of Discrete Mathematics. McGraw-Hill
R J Wilson & J Watkins. Graphs - an Introductory Approach. Wiley