MAT-62756 Graph Theory, 7 cr
Additional information
Suitable for postgraduate studies
Person responsible
Petteri Laakkonen
Lessons
Implementation 1: MAT-62756 2015-01
| Study type | P1 | P2 | P3 | P4 | Summer |
|
|
|
|
|
|
|
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:
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. | No |
Prerequisites
| Course | Mandatory/Advisable | Description |
| MAT-60006 Matrix Algebra | Advisable |
Correspondence of content
| Course | Corresponds course | Description |
| MAT-62756 Graph Theory, 7 cr | MAT-41196 Graph Theory, 6 cr |