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
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
