School of Mathematics and StatisticsHome | About the school | Contact | Courses | Research | Personnel list
MT4514 GRAPH THEORY
AimsTo introduce students to graph theory, as a tool for solving problems in mathematics and elsewhere, but also as an attractive study in its own right.
ObjectivesBy the end of the course students should know about topics such as the following and be able to solve problems in these areas.
- Applications of graph theory: Königsberg bridges, Knight's tours, puzzles, saturated hydrocarbons, network problems.
- Basic theory: isomorphism and degree.
- Eulerian graphs: basic theorem, Fleury's algorithm.
- Hamiltonian graphs: Hamilton's game, Dirac's theorem, Ore's theorem.
- Planar graphs: Euler's formula, Kuratowski's theorem, regular polyhedra.
- Colouring planar graphs: history of the four colour theorem, proof of the five colour theorem.
- Colouring other graphs: the chromatic number, the chromatic polynomial and algorithms for their calculation.
- Networks: the Maximal Flow problem, Minimal cuts and the Ford-Fulkerson algorithm, the shortest path algorithm. Critical Path analysis and the longest path algorithm.
- Ramsey theory: Ramsey's theorem, Ramsey numbers.
- Algebraic graph theory: the eigenvalue method.
- Graphical enumeration.
Students will be given the opportunity to use software packages to explore some of the above areas. Those studying the Symbolic Computation course (MT4111) can implement some of the above algorithms in MAPLE.
TextbooksIntroduction to Graph Theory: R J Wilson, Longman; 4th ed. 1996.
Graphs, an Introductory Approach: R J Wilson & J J Watkins, Wiley; 1990.
Assessment2 Hour Examination = 100%
PrerequisitesMT3501 or MT3503 or MT3504
AvailabilityAcademic year 2012/13 in semester 2 at 10
LecturerDr C Bleak
Click here for access to past examination papers for this module.
Click here to see the University Course Catalogue entry.
Revised: PMH (April 2012)