University of Wales, Bangor - Department of Mathematics Computer Science & Mathematics Year 3 Modules

Lecturer: Dr Chris Wensley

Recommended book:

• highly recommended:
  • Discrete and Combinatorial Mathematics: an applied introduction (3rd Ed), Ralph P Grimaldi, Addison Wesley, 1994, ISBN 0201549832 (QA39.2.G748).
  • Discrete Mathematics, Norman Biggs, Oxford 1988, ISBN 0198532520 (QA76.9.M35B54).
• additional reading
  • Graph Theory, Frank Harary, Addison-Wesley 1969
  • Algorithms, Robert Sedgewick, Addison-Wesley 1988, ISBN 0201066734 (QA76.6.S435)
  • Graph Theory, Ronald Gould, Benjamin/Cummings 1988 ISBN 08053060301 (QA166.G66)
  • A first course in Combinatorial Mathematics, Ian Anderson, Oxford 1974, ISBN 0198596162 (QA164.A5)

Aims:

• To introduce the basic language of graphs.
  
• To introduce the student to a range of applications of graph theory in organisational and optimising problems.
  
• To discuss the classification of graphs and their properties.

Objectives:
On completion of the module the student should know how to:

• Determine when a graph is Eulerian, Hamiltonian, planar, etc.
• Use these conditions to justify and apply a number of efficient algorithms to produce graphs with various properties.
• Apply the algorithms in various "real life" situations.

Summary:
Graph theory has a wide variety of applications, and we shall describe some of these applications to organisational and optimising problems. Specific areas addressed include Networks and flows; Euler and Hamiltonian graphs; trees and paths in graphs; planarity.

Prerequisites:
Be registered for a single or joint honours degree programme within the School of Informatics.

Syllabus:

Properties of Graphs:
Planar graphs. Euler characteristic. Colouring of graphs. 4-colour problem. Chromatic polynomial.

Euler and Hamiltonian Graphs:
Existence theorems and constructive algorithms. Applications to De Bruijn graphs and the Chinese Postman problem.

Trees:
Minimal Spanning Trees. Krusgal's algorithm. Shortest paths. Dijkstra's algorithm.
Travelling salesman problem and the idea of NP-completeness.
Algorithms for approximate solutions.

Networks:
Flows and Cuts. Max-flow min-cut theorem. Algorithms to find maximal flows, with constraints.
Flows between all pairs of vertices. The Complete Network.

Assessment:

• 2 hour end of semester closed book examination, 100%

School of Informatics home page Mathematics home page U. W. Bangor home page Latest modification to this page: 17/08/06