Graph Theory

Full course description

A graph is simply a collection of points, some of which are joined by lines. This deceptively simple structure is one of the cornerstones of both theoretical and applied computer science. A great many problems that arise in the real world can  be modeled as graph problems. Several classical examples include the problem of finding the shortest route between two cities, of maximizing flow in a network of pipelines, or of finding an optimal pairing between producers and consumers.  In this course we will look at both the algorithmic/applied side of graph theory and its more abstract mathematical foundations, because the latter is often important for understanding the former. We will cover topics such as paths, tours, trees, matchings, flows and colorings.