Graph Theory
Overall Course Objectives
The main aim of this course is to present to the students some basic results and proof techniques in graph theory, in particular in connection with networks algorithms.
See course description in Danish
Learning Objectives
- combine fundamental graph theoretic concepts and results to answer questions concerning the structure of graphs
- construct simple proofs of graph theoretic statements
- recognize different graph classes, such as, trees, bipartite graphs, complete graphs, and planar graphs.
- model a given problem as a graph problem
- apply graph algorithms to solve a given problem, e.g. shortest paths, maximum flow, maximal matching, minimum coverings, numbers of spanning trees, effective resistance, etc.
- modify known graph algorithms to solve a given problem
- argue for correctness of a graph algorithm
- analyze the complexity of graph algorithms
Course Content
Basic graph theory, including Euler graphs, Menger’s theorem on connectivity, planarity, matchings with applications to structure rank, scheduling problems. Network flows which constitute the foundation of combinatorial optimization with applications in e.g. operations research. Description and complexity of algorithms (shortest paths, spanning trees of minimal weight, the Chinese Postman’s problem, maximum matchings, job assignment) of interest in computer science. The mathematical foundation of electrical networks, including effective resistances expressed by spanning trees and determinants. Random walks.
Teaching Method
Lectures, exercises in groups, discussion of exercises in lecture room, home work exercises.