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

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.