# Graph Algorithms 2017

## 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

## Credits:

• 5sp

### Time schedule:

• Start date: 06th of September, 2017
• End date: 19th of October, 2017
• Wednesdays:
• 13-15, 115A, Agora, Vattenborgsvägen 5, 20500 ÅBO
• Thursdays:
• 15-17, 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
1:30 pm - 3:00 pm, 115A, Agora,
September 7, 2017
• September 7, 2017: Lecture 2: Graph search algorithms
3:15 pm - 5:00 pm, 115A, Agora,
September 13, 2017
• September 13, 2017: Lecture 3: Graph search algorithms (cont.)
1:30 pm - 3:00 pm, 115A, Agora,
September 14, 2017
• September 14, 2017: Lecture 4: Path searching algorithms
3:15 pm - 5:00 pm, 115A, Agora,
September 20, 2017
• September 20, 2017: Lecture 5: Path searching algorithms (cont.)
1:30 pm - 3:00 pm, 115A, Agora,
September 21, 2017
• September 21, 2017: Lecture 6: Minimum spanning trees, optimum branchings
3:15 pm - 5:00 pm, 115A, Agora,
September 27, 2017
• September 27, 2017: Lecture 7: Circuits, cut-sets and connectivity
1:30 pm - 3:00 pm, 115A, Agora,
September 28, 2017
• September 28, 2017: Lecture 8: Connectivity, cliques and independent sets
3:15 pm - 5:00 pm, 115A, Agora,
October 4, 2017
• October 4, 2017: Lecture 9: Cliques, independent sets, colouring
1:30 pm - 3:00 pm, 115A, Agora,
October 5, 2017
• October 5, 2017: Lecture 10: Tours: Euler, Hamiltonian paths. Travelling salesman problem
3:15 pm - 5:00 pm, 115A, Agora,
October 11, 2017
• October 11, 2017: Lecture 11: Tours: Euler, Hamiltonian paths. Travelling salesman problem
1:30 pm - 3:00 pm, 115A, Agora,
October 12, 2017
• October 12, 2017: Lecture 12: Graph matching
3:15 pm - 5:00 pm, 115A, Agora,
October 18, 2017
• October 18, 2017: Lecture 13: Network flow, Max flow problem
1:30 pm - 3:00 pm, 115A, Agora,
October 19, 2017
• October 19, 2017: Lecture 14: Network flow, Max flow problem. Min-cost flow problem
3:15 pm - 5:00 pm, 115A, Agora,

### Lecturer:

• Department of CS,
• Åbo Akademi University,
• vrogojin at abo.fi, room 342A, Agora, Vattenborgsvägen 5, 20500 ÅBO

• TBD

Through MinPlan.

## Projects

Here you can find currently opened projects for you and your gained scores General instructions: Input/Output files are text files. Graphs (both directed and undirected) are represented through list of edges unless stated otherwise in a particular project description. Input files are CSV (Comma Separated Values) tables with one record per row, columns are delimited …

## Graph Algorithms 2016

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 …

## Graph Algorithms 2014

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 …