Graphs and graph algorithms

Graphs and graph algorithms are of interest because: Graphs model a wide variety of phenomena, either directly or via construction, and also are embedded in system software and in many applications. Graph algorithms illustrate both a wide range of algorithmic designs and also a wide range of complexity behaviours, from linear and polynomial-time, to exponential-time algorithms. The aim is to: explore a little of the wide range of graph algorithms, introduce some of the relevant techniques, and consider what algorithms and performances are available, and the distinction between tractable and intractable problems. Algorithmic Problems on Graphs There is a wide range of computational tasks on graphs: Connectivity and components, Path-finding and traversals, including route finding, graph-searching, exhaustive cycles (Eulerian and Hamiltonian), Optimisation problems, eg shortest paths, maximum flows, travelling salesperson... Embedding problems, eg planarity- embedding in the plane, Matching (‘marriage problems’), graph colouring and partitioning, Graphs, trees and DAGs, including search trees, traversals, spanning trees, condensations, etc.