Module Identifier MA32410  
Module Title GRAPHS AND NETWORKS  
Academic Year 2007/2008  
Co-ordinator Professor V Mavron  
Semester Semester 1  
Other staff Professor V Mavron  
Pre-Requisite  
Course delivery Seminars / Tutorials   3 x 1 hour example classes  
  Lecture   19 x 1 hour lectures  
Assessment
Assessment TypeAssessment Length/DetailsProportion
Semester Exam2 Hours (written examination)  100%
Supplementary Assessment2 Hours (written examination)  100%

Learning outcomes

On completion of this module, students should be able to:
1.   investigate elementary properties of graphs;
2.   perform simple graph construction;
3.   represent abstract graphs diagrammatically;
4.   determine whether a graph satisfies various criteria;
5.   apply algorithms for finding components;
6.   describe the algorithms of Dijkstra and Floyd, and to apply them in simple cases;
7.   apply critical path analysis to simple projects;
8.   apply either Prim's or Kruskal's algorithm for finding optimum weight spanning trees;
9.   apply the Ford-Fulkerson algorithm to a transport network to find a maximum flow.

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

Aims

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.

Content

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

Books
** Recommended Text
N Biggs (1992) Discrete Mathematics Rev. ed.. OUP 0198534272
R P Grimaldi (1999) Discrete and Combinatorial Mathematics 4th. Addison-Wesley 0201304244
** Supplementary Text
C L Liu (1985) Elements of Discrete Mathematics 2nd. McGraw-Hill 007038133X
R J Wilson & J Watkins (1990) Graphs - an Introductory Approach Wiley 0471615544

Notes

This module is at CQFW Level 6