MAT-62756 Graph Theory, 7 cr

Additional information

Suitable for postgraduate studies. The implementation will not be executed during the academic year 2016-2017.

Person responsible

Petteri Laakkonen

Lessons

Implementation Period Person responsible Requirements
MAT-62756 2016-01 - Petteri Laakkonen
Closed-book written exam.

Learning Outcomes

After completing the course the student will identify graph and network structures in modeling. The student masters basic concepts, vocabulary, tools and properties of graphs and networks, and is able to use them in simple examples and modeling tasks. The student also masters basic graph-theoretical algorithms and is capable of implementing them in simple examples and applications. Completing the course gives the student skills for modelling and analyzing models using graph-theoretical methods. Nowadays these methods form perhaps the most general modelling tool in discrete mathematics and algorithmics, and therefore it is simply not possible to include outcomes for them all within a single course. Completing the course the student nevertheless should be able the generalize and extend the skills.

Content

Content Core content Complementary knowledge Specialist knowledge
1. Basic concepts and properties of graphs and digraphs. Matrix representations of graphs and digraphs. Fundamental cut sets and fundamental circuits, their properties and matrix representations.  Applying the given basic concepts, properties and representations in analyzing graphs and digraphs.   
2. Trees and directed trees and their basic characterization results. Spanning trees and forests. Quasi-strongly connected and acyclic digraphs.  Using trees and acyclic digraphs as a basic modeling tool. Stationary linear networks.   
3. Basic graph-theoretical algorithms and applying them in simple examples and applications.  The basic paradigms of graph algorithms and related algorithms with their variants: Dijkstra's algorithm, Floyd-Warshall algorithm, Kruskal's algorithm, Prim's algorithm, Ford-Fulkerson algorithm, search algorithms, annealing algorithms   
4. Geometric graph theory. Plane embeddings of graphs and planar graphs and their basic concepts, properties and algorithms. Drawing graphs. Elements of matroid theory.  Applying the given basic concepts and properties in analyzing planar graphs  Matroids and greedy algorithms. 

Instructions for students on how to achieve the learning outcomes

Final grade is determined from tutorial activity and the final closed-book exam. Passing the course requires passing the final exam, and for this at most half of the maximum points are required. Bonus points obtained by tutorial activity may be used to add the exam points according to a given scheme. A thorough mastering of the core content should be sufficient for passing the course with grade 3. To get the degree 4 at least some complementary knowledge is usually required, getting the grade 5 then requires a more thorough mastering of this knowledge.

Assessment scale:

Numerical evaluation scale (0-5)

Partial passing:

Completion parts must belong to the same implementation

Study material

Type Name Author ISBN URL Additional information Examination material
Book   Graph Theory and Its Applications   Gross, J.L. & Yellen, J.         No   
Book   Introduction to Graph Theory   West, D.B.         No   
Summary of lectures   Graafiteoria   Ruohonen, K.         No   
Summary of lectures   Graph Theory   Ruohonen, K.         Yes   

Prerequisites

Course Mandatory/Advisable Description
MAT-60006 Matrix Algebra Advisable    



Correspondence of content

Course Corresponds course  Description 
MAT-62756 Graph Theory, 7 cr YHTTAY-62750 Introduction to Graph Theory, 5 cr 1:1  
MAT-62756 Graph Theory, 7 cr MAT-41196 Graph Theory, 6 cr  

Updated by: Ikonen Suvi-Päivikki, 13.04.2016