|Taught under open university|
Scope and form:
Lectures, exercises in groups, discussion of exercises in lecture room, home work exercises.
Duration of Course:
Date of examination:
Type of assessment:
General 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 graph theoretic algorithms and with electrical networks.
|A student who has met the objectives of the course will be able to:|
- combine fundamental graph theoretic concepts and results to answer questions concerning the structure of graphs
- find distances, number of shortest paths, minimal spanning trees, and minimal walks through all edges
- find maximal flows and minimal cuts, critical and optimal edges
- find maximal matchings and minimal coverings in bipartite graphs, find maximal job assignments and optimum scheduling
- calculate Pauling bonds in benzoids
- apply current spaces and voltage spaces and Kirchhoff's tree theorem to find currents and voltages and driving point resticances in electrical networks
- calculate resistances in connection with random walks (Markov processes)
- apply Euler's formula to planar graphs
Basic graph theory, including Euler graphs, Menger's theorem on connectivity, planarity, matchings with applications to structure rank, scheduling problems, and Pauling bonds in benzoids. 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. Planar graphs.
|, 322, 008, (+45) 4525 3058,
|01 Department of Mathematics|
Registration Sign up:
|graph structure, network algorithms, electrical networks|
April 13, 2012|
See course in DTU Course base