Graph Theory

• 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

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.

01001/01003/01005/01017/01019, Mathematical maturity.

Lectures, exercises in groups, discussion of exercises in lecture room, home work exercises.