Single-Course Engelsk 5 ECTS

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.

Recommended prerequisites

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

Teaching Method

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

Faculty

See course in the course database.

Registration

Language

Engelsk

Duration

13 weeks

Institute

Compute

Place

DTU Lyngby Campus

Course code 01227
Course type Bachelor
Semester start Week 6
Semester end Week 20
Days Thurs 13-17
Price

9.250,00 DKK

Registration