Graph Theory and Applications

Table of Contents......Page 10
Introduction......Page 20
1.1 The origin of the graph concept......Page 24
1.2.1 Notation......Page 27
1.2.3 Terminology......Page 28
1.2.4 Isomorphism and unlabeled graphs......Page 29
1.2.5 Planar graphs......Page 30
1.3 Subgraphs......Page 31
1.4.1 Paths......Page 32
1.4.2 Cycles......Page 34
1.5 Degrees......Page 36
1.5.1 Regular graphs......Page 37
1.6 Connectedness......Page 38
1.7 Bipartite graphs......Page 39
1.8 Algorithmic aspects......Page 40
1.8.1 Representations of graphs inside amachine......Page 41
1.9 Exercises......Page 44
2.1 Definitions and properties......Page 48
2.1.1 First properties of trees......Page 49
2.1.3 Bridges......Page 50
2.1.4 Tree characterizations......Page 51
2.2 Spanning trees......Page 52
2.2.1 An interesting illustration of trees......Page 55
2.2.2 Spanning trees in a weighted graph......Page 56
2.3.1 The problem......Page 57
2.3.2 Kruskal’s algorithm......Page 58
2.3.3 Justification......Page 60
2.3.4 Implementation......Page 61
2.4 Connectivity......Page 62
2.4.1 Block decomposition......Page 63
2.4.2 k-connectivity......Page 64
2.4.3 k-connected graphs......Page 65
2.4.5 Edge connectivity......Page 66
2.4.6 k-edge-connected graphs......Page 67
2.4.8 Hypercube......Page 68
2.5 Exercises......Page 69
3.2 Edge coloring......Page 74
3.2.1 Basic results......Page 75
3.3 Algorithmic aspects......Page 76
3.4 The timetabling problem......Page 78
3.4.1 Roomconstraints......Page 79
3.4.2 An example......Page 81
3.5 Exercises......Page 84
4.1.2 Terminology......Page 86
4.1.3 Representation......Page 87
4.1.5 “Directed” concepts......Page 88
4.1.6 Indegrees and outdegrees......Page 89
4.1.7 Strongly connected components......Page 90
4.1.8 Representations of digraphs inside a machine......Page 91
4.2.1 Acyclic numbering......Page 93
4.2.2 Characterization......Page 94
4.3.1 Drawings......Page 95
4.3.2 Terminology......Page 96
4.3.3 Characterization of arborescences......Page 97
4.4 Exercises......Page 98
5.1 Depth-first search of an arborescence......Page 100
5.1.1 Iterative form......Page 101
5.1.2 Visits to the vertices......Page 103
5.1.4 Complexity......Page 105
5.2.1 The eight queens problem......Page 106
5.2.3 Associated arborescence......Page 108
5.2.5 The minimax algorithm......Page 109
5.2.6 Implementation......Page 110
5.2.8 Pruning......Page 111
5.3 Depth-first search of a digraph......Page 112
5.3.1 Comments......Page 113
5.3.2 Justification......Page 115
5.3.4 Extended depth-first search......Page 116
5.3.5 Justification......Page 117
5.3.7 Application to acyclic numbering......Page 118
5.3.8 Acyclic numbering algorithms......Page 119
5.4 Exercises......Page 120
6.1.1 A few definitions......Page 122
6.2 Case of non-weighted digraphs: breadth-first search......Page 123
6.2.1 Application to calculation of distances......Page 125
6.2.2 Justification and complexity......Page 126
6.2.3 Determining the shortest paths......Page 127
6.3 Digraphs without circuits......Page 128
6.3.3 Formulas......Page 130
6.4.1 Potential task graph......Page 131
6.4.2 Earliest starting times......Page 132
6.4.3 Latest starting times......Page 133
6.4.5 Free slacks......Page 134
6.4.7 Practical implementation......Page 136
6.5 Positive lengths......Page 137
6.5.1 Justification......Page 138
6.5.2 Associated shortest paths......Page 141
6.5.4 Undirected graphs......Page 143
6.6.1 Floyd’s algorithm......Page 145
6.7 Exercises......Page 146
7.1.1 A few definitions......Page 152
7.1.2 Concept of alternating paths and Berge’s theorem......Page 154
7.2 Matchings in bipartite graphs......Page 155
7.2.1 Matchings and transversals......Page 157
7.3.1 The Hungarian method......Page 159
7.3.2 Justification......Page 161
7.3.4 Complexity......Page 162
7.3.5 Maximum matching algorithm......Page 163
7.3.7 Complexity......Page 164
7.4 Optimal assignment problem......Page 167
7.4.1 Kuhn-Munkres algorithm......Page 168
7.4.2 Justification......Page 171
7.4.3 Complexity......Page 172
7.5 Exercises......Page 174
8.1 Flows in transportation networks......Page 176
8.1.1 Interpretation......Page 178
8.1.2 Single-source single-sink networks......Page 179
8.2 The max-flow min-cut theorem......Page 180
8.2.1 Concept of unsaturated paths......Page 181
8.3 Maximum flow algorithm......Page 183
8.3.1 Justification......Page 185
8.3.2 Complexity......Page 190
8.4 Flow with stocks and demands......Page 191
8.5.1 Menger’s theorem......Page 194
8.5.3 König’s theorem......Page 196
8.6 Exercises......Page 197
9.1 Euler trails and tours......Page 200
9.1.1 Principal result......Page 202
9.2 Algorithms......Page 204
9.2.1 Example......Page 205
9.2.4 The Rosenstiehl algorithm......Page 207
9.3 The Chinese postman problem......Page 210
9.3.1 The Edmonds-Johnson algorithm......Page 212
9.3.3 Example......Page 213
9.4 Exercises......Page 215
10.1 Hamilton cycles......Page 218
10.1.1 A few simple properties......Page 219
10.2 The traveling salesman problem......Page 221
10.2.2 Applications......Page 222
10.3 Approximation of a difficult problem......Page 223
10.3.1 Concept of approximate algorithms......Page 224
10.4.1 An approximate algorithm......Page 226
10.4.2 Justification and evaluation......Page 227
10.4.3 Amelioration......Page 229
10.4.5 Justification and evaluation......Page 230
10.4.6 Another approach......Page 233
10.4.7 Upper and lower bounds for the optimal value......Page 234
10.5 Exercises......Page 237
11.1 Planar graphs......Page 240
11.1.1 Euler’s relation......Page 241
11.1.2 Characterization of planar graphs......Page 243
11.2 Other graph representations......Page 245
11.2.2 Thickness......Page 246
11.3 Exercises......Page 247
12.1.1 Problem......Page 250
12.1.2 Comments......Page 251
12.2.2 Comments......Page 252
12.3.1 Problem......Page 254
12.4.1 Problem......Page 256
12.5.1 Problem......Page 257
12.5.2 Comments......Page 258
12.6.1 Problem......Page 259
12.6.2 Comments......Page 260
12.7.1 Problem......Page 261
12.7.2 Comments......Page 262
Appendix A. Expression of Algorithms......Page 264
A.2 Explanations and commentaries......Page 265
A.4 Comments......Page 268
B.1 The concept of complexity......Page 270
B.2 Class P......Page 272
B.3 Class NP......Page 275
B.4 NP-complete problems......Page 276
B.5 Classification of problems......Page 277
B.6 Other approaches to difficult problems......Page 279
Bibliography......Page 280
Index......Page 282