# ASO: Graph Theory - Material for the year 2019-2020

## Primary tabs

2019-2020

Lecturer(s):

Prof. Marc Lackenby

Course Term:

Trinity

Course Lecture Information:

8 lectures

Course Overview:

This course introduces some central topics in graph theory.

Learning Outcomes:

Students should have an appreciation of the flavour of methods and results in graph theory.

Course Synopsis:

Introduction. Paths, walks, cycles and trees. Euler circuits. Hall's theorem. Application and analysis of algorithms for minimum cost spanning trees, shortest paths, bipartite matching and the Chinese Postman Problem.

Reading List:

R. J. Wilson, *Introduction to Graph Theory*, 5th edition, Prentice Hall, 2010.

D.B. West, *Introduction to Graph Theory*, 2nd edition, Prentice Hall, 2001.