Graphs and applications: an introductory approach

Front cover......Page 1
Title page......Page 3
Date-line......Page 4
Preface......Page 5
Study Guide......Page 7
Contents......Page 9
1.1 Graphs, Digraphs and Networks......Page 13
1.2 Classifying Problems......Page 32
1.3 Seeking Solutions......Page 35
2.1 Graphs and Subgraphs......Page 37
2.2 Vertex Degrees......Page 47
2.3 Paths and Cycles......Page 50
2.4 Regular and Bipartite Graphs......Page 55
2.5 Case Studies......Page 62
Four Cubes Problem......Page 63
Social Netzvorks......Page 65
Exercises 2......Page 68
3.1 Exploring and Travelling......Page 73
3.2 Eulerian Graphs......Page 76
3.3 Hamiltonian Graphs......Page 83
Dominoes......Page 87
Diagram-Tracing Puzzles......Page 88
Knight\'s Tour Problem......Page 90
Gray Codes......Page 92
Exercises 3......Page 94
4.1 Digraphs and Subdigraphs......Page 96
4.2 Vertex Degrees......Page 104
4.3 Paths and Cycles......Page 106
4.4 Eulerian and Hamiltonian Digraphs......Page 109
Ecology......Page 111
Social Networks......Page 113
Rotating Drum Problem......Page 116
Ranking in Tournaments......Page 118
Exercises 4......Page 120
5 Matrix Representations......Page 124
5.1 Adjacency Matrices......Page 125
5.2 Walks in Graphs and Digraphs......Page 129
5.3 Incidence Matrices......Page 134
Interval Graphs......Page 138
Markov Chains......Page 141
Exercises 5......Page 145
6 Tree Structures......Page 150
6.1 Mathematical Properties of Trees......Page 152
6.2 Spanning Trees......Page 156
6.3 Rooted Trees......Page 158
Braced Rectangular Frameworks......Page 164
Exercises 6......Page 173
7 Counting Trees......Page 175
7.1 Counting Labelled Trees......Page 176
7.2 Counting Binary Trees......Page 183
7.3 Counting Chemical Trees......Page 186
Exercises 7......Page 193
8.1 Minimum Connector Problem......Page 194
8.2 Travelling Salesman Problem......Page 203
Exercises 8......Page 210
9.1 Fleury\'s Algorithm......Page 214
9.2 Shortest Path Algorithm......Page 216
Chinese Postman Problem......Page 224
Exercises 9......Page 226
10.1 Connected Graphs and Digraphs......Page 228
10.2 Menger\'s Theorem for Graphs......Page 238
10.3 Some Analogues of Menger\'s Theorem......Page 242
Reliable Telecommunication Networks......Page 248
Exercises 10......Page 251
11 Planarity......Page 254
11.1 Planar Graphs......Page 255
11.2 Euler\'s Formula......Page 259
11.3 Cycle Method for Planarity Testing......Page 268
11.4 Kuratowski\'s Theorem......Page 272
11.5 Duality......Page 276
11.6 Convex Polyhedra......Page 280
Exercises 11......Page 286
12.1 Vertex Colourings......Page 289
12.2 Algorithm for Vertex Colouring......Page 300
12.3 Vertex Decompositions......Page 304
Exercises 12......Page 311
13.1 Edge Colourings......Page 315
13.2 Algorithm for Edge Colouring......Page 325
13.3 Edge Decompositions......Page 329
Exercises 13......Page 341
14.1 Classification of Problems......Page 344
14.2 Efficiency of Algorithms......Page 350
14.3 Another Classification of Problems......Page 351
Suggestions for Further Reading......Page 358
Appendix: Methods of Proof......Page 360
Computing Notes......Page 366
Solutions to Computer Activities......Page 392
Solutions to Problems in the Text......Page 396
Index......Page 451
Back Cover......Page 457