- Lecturer: Marc Lackenby
General Prerequisites:
Course Term: Trinity
Course Lecture Information: 8 lectures
Course Overview:
This course introduces some central topics in graph theory.
Learning Outcomes:
By the end of the course, students should have an appreciation of the methods and results of graph theory. They should have a good understanding of the basic objects in graph theory, such as trees, Euler circuits and matchings, and they should be able to reason effectively about graphs.
Course Synopsis:
Introduction. Paths, walks, cycles and trees. Euler circuits. Hamiltonian cycles. Hall's theorem. Application and analysis of algorithms for minimum cost spanning trees, shortest paths, bipartite matching and the Chinese Postman Problem.