TCS / Studies / S-72.2420/T-79.5203 Graph Theory

# S-72.2420 / T-79.5203 Graph Theory (5 cr) P

## Spring 2008

[Current] [General Information] [Lectures] [Tutorials] [WebOodi] [Spring 2007]

Graph theory is arguably one of the most studied topics in contemporary discrete mathematics, and its theoretical and applied importance is constantly growing. Graph-theoretic problems are encountered in diverse applications such as bioinformatics and decoding algorithms in telecommunications --- not to mention the more traditional applications such as routing, flow problems, and project scheduling. Although sporadic graph-theoretic concepts and results are encountered also in other courses taught here at TKK, the aim of this course is to provide a more in-depth introduction to graph theory.

The course is divided into two parts, theory and algorithms. The theory part covers basic types of graphs and central graph theoretic concepts such as distance, symmetry, coloring, connectivity, planarity, and so forth. A further goal is to learn logical reasoning together with tools and proof techniques commonly applied in discrete mathematics. The algorithm part reviews some of the central graph algorithms/problems such as depth- and breadth-first search together with their numerous applications, shortest path, minimum spanning tree, maximum matching, maximum flow, and so forth. Here one central aim is to understand the connection between a mathematical result and the algorithm that exploits it. Associated with the algorithm part is a programming project.

The course is organized jointly by the Department of Communications and Networking and the Department of Information and Computer Science. The course is also recommended to mathematically oriented students from other departments.

## Current

April 25
Project review for the programming project.
March 27
The first tutorial session.
March 14
The first lecture.
January 3
The lectures start on March 14. Registration is via [WebOodi] (course S-72.2420).

## General Information

• Prerequisites: Basic courses in mathematics and computer science.
• Literature: D. B. West, Introduction to Graph Theory, 2nd ed., Prentice Hall, Upper Saddle River NJ, 2001. D. Jungnickel, Graphs, Networks and Algorithms, 2nd ed., Springer, Berlin, 2005.
• Electronic literature: R. Diestel, Graph Theory, 3rd ed., Springer, Heidelberg, 2005.
• Lectures: Wednesdays 9-12, hall T4 (Konemiehentie 2) and Fridays 9-12, hall T4 (Konemiehentie 2). First lecture: March 14.
• Teachers: D.Sc.(Tech.) Petteri Kaski (contact information), Prof. Patric Östergård (contact information).
• Tutorials: Mondays 10-12, hall T4 (Konemiehentie 2) and Thursdays 10-12, hall T4 (Konemiehentie 2). First tutorial session: March 27.
• Assistant: M.Sc.(Tech.) Olli Pottonen, room I436 (Otakaari 5), tel. 451 2350, e-mail: olli(dot)pottonen(at)tkk(dot)fi.
• Grading: Exam and programming project.
• Exam: May 14, 2008, 9-12, hall T1 (Konemiehentie 2).
• Registration: Registration is via [WebOodi] (course S-72.2420).
• Newsgroup: opinnot.tik.graafiteoria

## Lectures

March 14
Practical arrangements; introduction
March 19
Basic concepts
March 21
Easter holiday (no lecture)
March 26
Easter holiday (no lecture)
March 28
Trees and distance; graph parameters
April 2
Connectivity; coloring
April 4
Planarity; edges and cycles, Ramsey theory; random graphs
April 9
Searching a graph; applications
April 11
Shortest paths and minimum spanning trees
April 16
Matching in bipartite and general graphs
April 18
Flows and circulations
April 23
The deletion–contraction algorithm and graph polynomials
April 25
Project review for the programming project

Also available is an English-Finnish-Swedish dictionary consisting of some central graph-theoretic terms.

## Tutorials

The tutorial problems and solutions are available here.
[TKT pääsivu] [Yhteystiedot] [Henkilöstö] [Tutkimus] [Julkaisut] [Ohjelmistot] [Opinnot] [Uutisarkisto] [Linkkejä]
Päivitetty viimeksi 23.04.2008.