Sehr Interessant für Mathematiker

Algorithmic Discrete
Mathematics
Lecture notes, Summer term 2017
Andreas Paffenholz, Silke Horn, Marc Pfetsch




version of July 26, 2017

,version of July 26, 2017

,Contents
Contents 1

List of Figures 3

List of Algorithms 5

Timeline 7

0 Introduction 11

1 Basic Graph Theory 13
1.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 13
1.2 Graphs and Basic Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
1.3 Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23

2 Algorithms and Data Structures 29
2.1 Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
2.2 Growth of Functions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
2.3 Running Time of Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32
2.4 Data Types and Representations of Graphs . . . . . . . . . . . . . . . . . . . . . . . 33
2.4.1 Data Types . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.4.2 Data Structures for Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . 34
2.5 Sorting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36

3 Basic Graph Algorithms 41
3.1 Graph Traversal . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41
3.2 Minimal Spanning Trees . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

4 Shortest Paths 51
4.1 Directed Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 51
4.2 Dijkstra’s Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 54
version of July 26, 2017




4.3 The Bellman-Ford-Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56

5 Flows 61
5.1 Networks and Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61
5.2 Maximal Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62
5.3 The Ford-Fulkerson-Method . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63
5.4 Integral Flows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65
5.5 Path Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 68

1

, 6 Matchings 69
6.1 Basic Definitions and Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69
6.2 Matchings in Bipartite Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

7 Complexity 75
7.1 P and NP . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75
7.2 NP-Completeness . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77
version of July 26, 2017




2