Cover......Page 1
Half Title......Page 2
Textbooks in Mathematics......Page 3
Title......Page 4
Copyright......Page 5
Dedication......Page 6
CONTENTS......Page 8
PREFACE......Page 12
AUTHORS......Page 14
Chapter 1 INTRODUCTION TO GRAPH MODELS......Page 16
1.1 GRAPHS AND DIGRAPHS......Page 17
1.2 COMMON FAMILIES OF GRAPHS......Page 30
1.3 GRAPH MODELING APPLICATIONS......Page 37
1.4 WALKS AND DISTANCE......Page 44
1.5 PATHS, CYCLES, AND TREES......Page 55
1.6 VERTEX AND EDGE ATTRIBUTES: MORE APPLICATIONS......Page 64
1.7 SUPPLEMENTARY EXERCISES......Page 68
GLOSSARY......Page 69
Chapter 2 STRUCTURE AND REPRESENTATION......Page 74
2.1 GRAPH ISOMORPHISM......Page 75
2.2 AUTOMORPHISMS AND SYMMETRY......Page 83
2.3 SUBGRAPHS......Page 89
2.4 SOME GRAPH OPERATIONS......Page 98
2.5 TESTS FOR NON-ISOMORPHISM......Page 108
2.6 MATRIX REPRESENTATIONS......Page 115
2.7 MORE GRAPH OPERATIONS......Page 120
2.8 SUPPLEMENTARY EXERCISES......Page 128
GLOSSARY......Page 130
Chapter 3 TREES......Page 136
3.1 CHARACTERIZATIONS AND PROPERTIES OF TREES......Page 137
3.2 ROOTED TREES, ORDERED TREES, AND BINARY TREES......Page 145
3.3 BINARY-TREE TRAVERSALS......Page 153
3.4 BINARY-SEARCH TREES......Page 158
3.5 HU MAN TREES AND OPTIMAL PRE X CODES......Page 163
3.6 PRIORITY TREES......Page 167
3.7 COUNTING LABELED TREES: PR UFER ENCODING......Page 172
3.8 COUNTING BINARY TREES: CATALAN RECURSION......Page 178
3.9 SUPPLEMENTARY EXERCISES......Page 180
GLOSSARY......Page 183
Chapter 4 SPANNING TREES......Page 188
4.1 TREE GROWING......Page 189
4.2 DEPTH-FIRST AND BREADTH-FIRST SEARCH......Page 196
4.3 MINIMUM SPANNING TREES AND SHORTEST PATHS......Page 201
4.4 APPLICATIONS OF DEPTH-FIRST SEARCH......Page 208
4.5 CYCLES, EDGE-CUTS, AND SPANNING TREES......Page 216
4.6 GRAPHS AND VECTOR SPACES......Page 222
4.7 MATROIDS AND THE GREEDY ALGORITHM......Page 233
4.8 SUPPLEMENTARY EXERCISES......Page 238
GLOSSARY......Page 239
Chapter 5 CONNECTIVITY......Page 244
5.1 VERTEX- AND EDGE-CONNECTIVITY......Page 245
5.2 CONSTRUCTING RELIABLE NETWORKS......Page 250
5.3 MAX-MIN DUALITY AND MENGER'S THEOREMS......Page 258
5.4 BLOCK DECOMPOSITIONS......Page 267
5.5 SUPPLEMENTARY EXERCISES......Page 271
GLOSSARY......Page 272
Chapter 6 OPTIMAL GRAPH TRAVERSALS......Page 274
6.1 EULERIAN TRAILS AND TOURS......Page 275
6.2 DEBRUIJN SEQUENCES AND POSTMAN PROBLEMS......Page 279
6.3 HAMILTONIAN PATHS AND CYCLES......Page 294
6.4 GRAY CODES AND TRAVELING SALESMAN PROBLEMS......Page 299
6.5 SUPPLEMENTARY EXERCISES......Page 309
GLOSSARY......Page 310
Chapter 7 PLANARITY AND KURATOWSKI'S THEOREM......Page 312
7.1 PLANAR DRAWINGS AND SOME BASIC SURFACES......Page 313
7.2 SUBDIVISION AND HOMEOMORPHISM......Page 320
7.3 EXTENDING PLANAR DRAWINGS......Page 324
7.4 KURATOWSKI'S THEOREM......Page 331
7.5 ALGEBRAIC TESTS FOR PLANARITY......Page 339
7.6 PLANARITY ALGORITHM......Page 352
7.7 CROSSING NUMBERS AND THICKNESS......Page 355
7.8 SUPPLEMENTARY EXERCISES......Page 360
GLOSSARY......Page 362
Chapter 8 GRAPH COLORINGS......Page 366
8.1 VERTEX-COLORINGS......Page 367
8.2 MAP-COLORINGS......Page 382
8.3 EDGE-COLORINGS......Page 389
8.4 FACTORIZATION......Page 403
8.5 SUPPLEMENTARY EXERCISES......Page 408
GLOSSARY......Page 410
Chapter 9 SPECIAL DIGRAPH MODELS......Page 414
9.1 DIRECTED PATHS AND MUTUAL REACHABILITY......Page 415
9.2 DIGRAPHS AS MODELS FOR RELATIONS......Page 426
9.3 TOURNAMENTS......Page 432
9.4 PROJECT SCHEDULING......Page 437
9.5 FINDING THE STRONG COMPONENTS OF A DIGRAPH......Page 444
9.6 SUPPLEMENTARY EXERCISES......Page 450
GLOSSARY......Page 451
Chapter 10 NETWORK FLOWS AND APPLICATIONS......Page 456
10.1 FLOWS AND CUTS IN NETWORKS......Page 457
10.2 SOLVING THE MAXIMUM-FLOW PROBLEM......Page 465
10.3 FLOWS AND CONNECTIVITY......Page 475
10.4 MATCHINGS, TRANSVERSALS, AND VERTEX COVERS......Page 484
10.5 SUPPLEMENTARY EXERCISES......Page 497
GLOSSARY......Page 498
Chapter 11 GRAPH COLORINGS AND SYMMETRY......Page 502
11.1 AUTOMORPHISMS OF SIMPLE GRAPHS......Page 503
11.2 EQUIVALENCE CLASSES OF COLORINGS......Page 508
11.3 SUPPLEMENTARY EXERCISES......Page 514
GLOSSARY......Page 515
A.1 LOGIC FUNDAMENTALS......Page 516
A.2 RELATIONS AND FUNCTIONS......Page 517
A.3 SOME BASIC COMBINATORICS......Page 520
A.4 ALGEBRAIC STRUCTURES......Page 521
A.5 ALGORITHMIC COMPLEXITY......Page 526
A.6 SUPPLEMENTARY READING......Page 529
B.1 GENERAL READING......Page 530
B.2 REFERENCES......Page 532
SOLUTIONS AND HINTS......Page 538
INDEX OF APPLICATIONS......Page 578
INDEX OF ALGORITHMS......Page 580
GENERAL INDEX......Page 582