School of Mathematics and StatisticsHome  About the school  Contact  Courses  Research  Personnel list 
Courses in

MT4514 GRAPH THEORYAimsTo 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 FordFulkerson 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 MT3504AvailabilityAcademic year 2012/13 in semester 2 at 10
LecturerDr C BleakClick here for access to past examination papers for this module.
Click here to see the University Course Catalogue entry. Revised: PMH (April 2012)
