Description
The goal of this course is to demonstrate how graph theory can be used to solve real-life problems. We will consider a number of major problems on graphs such as graph exploration, optimal paths search, tours on graphs, optimal network flow, etc., and will demonstrate a number of exact and approximation algorithms solving them. We will analyze the algorithms complexities and discuss their implementations.Content: Search on graphs – depth-first search and breadth-first search algorithms; Optimal path search – cheapest/shortest/longest path search algorithms; Connectivity in graphs – edge and vertex connectivity, connected components; Minimum spanning trees; Cliques, independent sets, coloring; Graph tours – Euler, Hamiltonian paths. Traveling salesman problem; Graph matching; Network flow – Max flow problem. Min-cost flow problem;