Crest

School of Mathematics and Statistics

Home | About the school | Contact | Courses | Research | Personnel list

Courses in
Mathematics
and Statistics

Level 1 Modules

Level 2 Modules

Level 3 Modules

Level 4 Modules

Level 5 Modules


Timetable

2013/2014 Sem. 1

2013/2014 Sem. 2


MT4514 GRAPH THEORY


Aims

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

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.

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

Textbooks

Introduction to Graph Theory: R J Wilson, Longman; 4th ed. 1996.

Graphs, an Introductory Approach: R J Wilson & J J Watkins, Wiley; 1990.

Assessment

2 Hour Examination = 100%

Prerequisites

MT3501 or MT3503 or MT3504

Availability

Academic year 2012/13 in semester 2 at 10

Lecturer

Dr 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)


Found a problem with the site? Click here and let us know.