Course Catalog 2014-2015
International

Basic Pori International Postgraduate Open University

|Degrees|     |Study blocks|     |Courses|    

Course Catalog 2014-2015

MAT-62756 Graph Theory, 7 cr

Additional information

Suitable for postgraduate studies

Person responsible

Esko Turunen, Keijo Ruohonen, Petteri Laakkonen

Lessons

Study type P1 P2 P3 P4 Summer Implementations Lecture times and places
Lectures
Excercises
 4 h/week
 2 h/week
+4 h/week
+2 h/week


 


 


 
MAT-62756 2014-01 Wednesday 12 - 14 , TB223
Friday 10 - 12 , TB223
Wednesday 12 - 14 , TB224

Requirements

Closed-book written exam.
Completion parts must belong to the same implementation

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 (1-5) will be used on the course

Partial passing:

Completion parts must belong to the same implementation

Study material

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

Prerequisites

Course Mandatory/Advisable Description
MAT-60006 Matrix Algebra Advisable    

Prerequisite relations (Requires logging in to POP)



Correspondence of content

Course Corresponds course  Description 
MAT-62756 Graph Theory, 7 cr MAT-41196 Graph Theory, 6 cr  

More precise information per implementation

Implementation Description Methods of instruction Implementation
MAT-62756 2014-01 Graph Theory lectures and tutorials in Fall 2014.       Contact teaching: 0 %
Distance learning: 0 %
Self-directed learning: 0 %  

Last modified25.06.2014