Course Catalog 2010-2011
International

Basic Pori International Postgraduate Open University

|Degrees|     |Study blocks|     |Courses|    

Course Catalog 2010-2011

MAT-41196 Graph Theory, 6 cr

Person responsible

Keijo Ruohonen

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-41196 2010-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

Principles and baselines related to teaching and learning

-

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-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, search algorithms, annealing algorithms   
4. Geometric graph theory. Plane embedings 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. 

Evaluation criteria for the course

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.            English  
Other online content   Course page              English  
Summary of lectures   Graph Theory   Ruohonen, K.            English  

Prerequisite relations (Requires logging in to POP)

Correspondence of content

There is no equivalence with any other courses

Additional information

Suitable for postgraduate studies

More precise information per implementation

Implementation Description Methods of instruction Implementation
MAT-41196 2010-01 Graph Theory lectures and tutorials in Fall 2010.        

Last modified09.02.2010