| 01227 Graph Theory |
| Danish title: Grafteori |
|
Language: English ECTS-creditpoints: 5, External examination.
|
|
|
Exam schedule:
|
E1-B (dec 11 2001), F1-B (maj 28 2002) |
| Recommended semester: 4th -7th semester |
| Scope and form: Lectures, exercises in groups, discussion of exercises in lecture room, home work exercises. |
| Evaluation: Written exam
|
| Examination: 13-scale |
| Previous course: C0127 |
| Prerequisites: 01010 / 01011 or 01000 / 01001,01012 / 01013 / 01014, or 01005 / 01015 / 01016 |
| No credit points with: C0127 |
| Aim: 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. |
| Contents: 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. |
| Contact: Carsten Thomassen, building 303, (+45) 4525 3058, c.thomassen@mat.dtu.dk |
| Department: 001 Department of Mathematics |
| Course URL: http://www.mat.dtu.dk/courses/01227 |
| Keywords: graph structure, network algorithms, electrical networks |
| Updated: 19-04-2001 |
|
|
