[an error occurred while processing this directive]
MT3814 GRAPH THEORY
Aims
To introduce students to the study of graph theory as a tool for representing connections between data in a variety of other fields and to show how graph theoretic methods can be used to solve problems in mathematics and elsewhere.
Objectives
By the end of the course students should know about topics such as the following and be able to solve problems in these areas.
1. Applications of graph theory: Kšnigsberg bridges, Knight's tours, parse trees, saturated hydrocarbons.
2. Basic theory: isomorphism and degree.
3. Eulerian graphs: basic theorem, Fleury's algorithm.
4. Hamiltonian graphs: Hamilton's game, Dirac's theorem, Ore's theorem.
5. Planar graphs: Euler's formula, Kuratowski's theorem, the Glasgow algorithm, regular polyhedra.
6. Colouring planar graphs: history of the four colour theorem, proof of the five colour theorem.
7. Colouring other graphs: the chromatic number, the chromatic polynomial and algorithms for their calculation.
8. Trees: labelled trees and Prźfer sequences.
9. Application of trees: The Shortest Path Problem, mazes, the Minimal Spanning Tree problem, the Travelling Salesman Problem.
10. Networks: the Maximal Flow problem, Minimal cuts and the Ford-Fulkerson algorithm. Critical Path analysis and the Longest Path algorithm.
11. Matching Problems: Hall's marriage problem and Hall's conditions, edge colouring and Latin squares.
12. Applications to groups: the Cayley graph, the Loop Basis theorem.
Students will be given the opportunity to use the MacTutor package to explore some of the above areas. Those studying the Symbolic Computation course (MT3611) can implement some of the above algorithms in MAPLE.
Textbooks
Graphs, an Introductory Approach: R J Wilson & J J Watkins, Wiley; 1990.
Introduction to Graph Theory: R J Wilson, Longman; 1975.
Prerequisite(s)
MT2002
Availability
It will next be taught in the academic year beginning in 2002, in Semester 2.
Lecturer(s)
Professor K J FALCONER (Mathematical Institute Room 203)
Click here to see the University Course Catalogue entry.
Revised: FIPS ( JULY 2001)
Found a problem with the site?
Click here and
let us know.
