Description
In mathematics and computer science, graph theory is the study of graphs, which are mathematical structures used to model pairwise relations between objects. One can “observe graphs” everywhere. Virtually, any field of science, industry, commerce, politics, social life, etc. contains numerous cases of relations and processes that could be naturally represented in terms of graphs. One would need to apply computational methods from graph theory to address the related problems from real life. During this course we study a number of graph algorithms and discuss their implementation.
The goal of this course is to demonstrate how graph theory can be used to solve reallife problems. We consider here a number of major problems on graphs such as graph exploration, optimal paths search, tours on graphs, optimal network flow, etc., and demonstrate a number of exact and approximation algorithms solving them. We analyze the algorithms complexities and discuss their implementations.
Particularly, we focus on the following topics:
 basic computational problems from graph theory and their relation to real life cases;
 algorithms solving graph theoretic problems and analyze their complexity;
 implementation of the algorithms on graphs.
Content
 search on graphs – depthfirst search and breadthfirst 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. Mincost flow problem;
Prerequisites
 Preferably: discrete mathematics concepts and graph theory (brief introduction of necessary concepts and notions will be given whenever necessary)
 Some knowledge and skills in programming is appreciated, especially in Java language.
Course format
 Lectures: 28h, 14 lectures
 Exercises: 7 homework+demonstration sessions
 Final examination:
 15 points – pass, mark 1/5
 over 27 points , mark 5/5
 Bonus points from exercises
 with enough gained bonus points one can skip the final exam, and even obtain the highest mark
Literature:
 Course book: Alan Gibbons, Algorithmic Graph Theory, Cambridge University Press, 1985
 James A. McHugh, Algorithmic Graph Theory, Prentice Hall, 1989
 Graph Algorithms, http://en.wikipedia.org/wiki/Book:Graph_Algorithms
Credits:
 5sp
Time schedule:
 Start date: 06th of September, 2017
 End date: 19th of October, 2017
 Wednesdays:
 1315, 115A, Agora, Vattenborgsvägen 5, 20500 ÅBO
 Thursdays:
 1517, 115A, Agora, Vattenborgsvägen 5, 20500 ÅBO
 Course exams:
 03.11.2017
 24.11.2017
 Check the list below for more details (SUBJECT OF CHANGE):
 September 6, 2017


September 6, 2017: Lecture 1: Introduction

 September 7, 2017


September 7, 2017: Lecture 2: Graph search algorithms

 September 13, 2017


September 13, 2017: Lecture 3: Graph search algorithms (cont.)

 September 14, 2017


September 14, 2017: Lecture 4: Path searching algorithms

 September 20, 2017


September 20, 2017: Lecture 5: Path searching algorithms (cont.)

 September 21, 2017


September 21, 2017: Lecture 6: Minimum spanning trees, optimum branchings

 September 27, 2017


September 27, 2017: Lecture 7: Circuits, cutsets and connectivity

 September 28, 2017


September 28, 2017: Lecture 8: Connectivity, cliques and independent sets

 October 4, 2017


October 4, 2017: Lecture 9: Cliques, independent sets, colouring

 October 5, 2017


October 5, 2017: Lecture 10: Tours: Euler, Hamiltonian paths. Travelling salesman problem

 October 11, 2017


October 11, 2017: Lecture 11: Tours: Euler, Hamiltonian paths. Travelling salesman problem

 October 12, 2017


October 12, 2017: Lecture 12: Graph matching

 October 18, 2017


October 18, 2017: Lecture 13: Network flow, Max flow problem

 October 19, 2017


October 19, 2017: Lecture 14: Network flow, Max flow problem. Mincost flow problem

Lecturer:
 Vladimir Rogojin,
 Department of CS,
 Åbo Akademi University,
 vrogojin at abo.fi, room 342A, Agora, Vattenborgsvägen 5, 20500 ÅBO
Course assistant:
 TBD
Registration (also for the exam)
Through MinPlan.