## 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 real-life 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 – 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;

## 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:**10th of March, 2014**End date:**8th of May, 2014**BREAK:**13th of March – 20th of March**Mondays:**- 10-12, Cobol,
**Exception: 7th of April, Algol!!!**- Break: 21st of April
*(Easter Monday)*

**Thursdays:**- 13-15, Cobol,
**Exception: 3rd and 10th of April, Fortran!!!**- Break: 1st of May (May Day)

**Exercise demonstrations:**- Thursdays at 10, Algol,
- First session: 20th of March,
- 7 sessions

- Check the list below for more details (SUBJECT OF CHANGE):

[google-calendar-events id=”874″ type=”list”]

### Lecturer:

- Vladimir Rogojin,
- Department of IT,
- Åbo Akademi University,
- vrogojin at abo.fi, room B5078, ICT-house

### Course assistant:

- Bogdan Iancu,
- Department of IT,
- Åbo Akademi University,
- biancu at abo.fi, room B5058, ICT-house