Graph Theory with Applications

Cover
......Page 1
Preface
......Page 8
Contents......Page 12
1.1 What is a Graph ? Definition
......Page 22
1.2.2. Un-directed graph
......Page 24
1.3.5. Finite and Infinite graphs
......Page 25
1.6 The Handshaking Theorem
......Page 26
1.7.2. Complete graph
......Page 41
1.7.6. Platonic graph
......Page 42
1.7.7. N-cube
......Page 43
1.8.1. Spanning subgraph
......Page 46
1.8.3. Induced subgraph
......Page 47
1.9 Graphs Isomorphism
......Page 48
1.10.1. Union
......Page 63
1.10.4. Ring sum
......Page 64
1.10.6. Composition
......Page 65
1.10.8. Fusion
......Page 66
1.11 The Problem of Ramsey
......Page 67
1.12 Connected and Disconnected Graphs
......Page 70
1.12.1. Path graphs and cycle graphs
......Page 71
1.12.2. Rank and nullity
......Page 72
1.13.1. Walk
......Page 77
1.13.3. Circuit
......Page 78
1.13.4. Length
......Page 79
1.14.2. Euler circuit
......Page 83
1.15 Fleury’s Algorithm
......Page 93
1.16 Hamiltonian Graphs
......Page 96
1.17 Dirac’s Theorem
......Page 97
1.18 Ore’s Theorem
......Page 99
1.19 Problem of Seating Arrangement
......Page 108
1.20 Traveling-Salesman Problem
......Page 109
1.22.1. Matrix Representation
......Page 111
1.22.2 (b) Representation of directed graph
......Page 112
1.22.4. Linked representation
......Page 113
Problem Set 1.1
......Page 120
2.1 Combinatorial and Geometric Graphs (Representation)
......Page 129
2.2 Planar Graphs
......Page 130
2.4 Homeomorphic Graphs
......Page 131
2.5 Region
......Page 132
2.8 Inner Vertex Set
......Page 133
2.10 Crossing Number
......Page 134
2.11.1. Complete bipartite graph
......Page 135
2.12 Euler’s Formula
......Page 137
2.12.1. Three utility problem
......Page 147
2.12.2. Kuratowski’s Theorem
......Page 158
2.13 Detection of Planarity of a Graph
......Page 159
2.14 Dual of a Planar Graph
......Page 165
2.14.3. Self-dual graphs......Page 166
2.14.5. Dual of a homeomorphic graph......Page 167
2.14.6. Abstract dual
......Page 168
2.15.1. Partitioning problem
......Page 174
2.15.3. Chromatic number
......Page 175
2.16 Chromatic Polynomial
......Page 176
2.16.1. Decomposition Theorem
......Page 178
2.16.3. Frequency assignments
......Page 185
2.16.4. Index registers
......Page 186
2.17 Colour Problem
......Page 203
2.17.1. The Four colour theorem
......Page 204
2.17.2. The Five colour theorem
......Page 206
Problem Set 2.1
......Page 207
3.1.3. Forest
......Page 213
3.3.1. Co tree
......Page 214
3.4 Binary Trees
......Page 215
3.4.1. Path length of a binary tree
......Page 216
3.4.2. Binary tree representation of general trees
......Page 217
3.5. Counting Trees
......Page 236
3.5.1. Cayley theorem
......Page 238
3.7. Complete Binary Tree
......Page 243
3.7.1. Almost complete binary tree
......Page 244
3.8.1. Infix notation
......Page 245
3.8.4. Evaluating prefix and postfix form of an expression
......Page 246
3.9. Binary Search Trees
......Page 247
3.10.1. Sequential Representation
......Page 248
3.10.2. Linked representation
......Page 249
3.11.2. DFS algorithm
......Page 256
3.12.2. The complexity of sorting algorithms
......Page 269
3.12.3. The merge sort algorithms
......Page 270
3.13. Weighted Trees and Prefix Codes
......Page 274
3.13.1. Huffman coding
......Page 275
3.14.1. The minimum connector problem
......Page 283
3.14.2. Enumeration of chemical molecules
......Page 284
3.14.3. Electrical neworks
......Page 285
Problem Set 3.1
......Page 287
4.2 Dijkstra’s Algorithm
......Page 299
4.2.2. Floyd-Warshall algorithm
......Page 300
4.3.2. Minimal spanning tree......Page 311
4.3.4. Kruskal’s algorithm......Page 312
4.3.5. Prim’s algorithm......Page 324
4.3.6. The labeling algorithm......Page 337
4.3.8. Distance and diameter......Page 342
4.3.9. Cut vertex, cut set and bridge
......Page 343
4.3.14. Edge connectivity......Page 344
4.3.15. Vertex connectivity
......Page 345
4.4 Transport Networks
......Page 351
4.5 Max–Flow Min–Cut Theorem
......Page 357
4.6 Matching Theory
......Page 365
4.7 Hall’s Marriage Theorem
......Page 371
Problem Set 4.1
......Page 385
5.4 Independent (Matroids) Sets
......Page 388
5.8.4. Trivial matroids......Page 389
5.8.8. Cographic matroids......Page 390
5.8.12. Representable matroids......Page 391
5.8.13. Restrictions and contractions
......Page 392
5.9.3. Marriage problem......Page 395
5.9.5. Common transversals......Page 396
5.9.9. Vertex-disjoint paths......Page 397
5.9.11. vw-separating set
......Page 398
Problem Set 5.1
......Page 405
6.1 Types of Enumeration
......Page 408
6.3 Counting Labeled Trees
......Page 409
6.6 Enumeration of Trees
......Page 410
6.8 Generating Functions
......Page 411
6.10 Rooted Unlabeled Trees
......Page 412
6.12 Free Unlabeled Trees
......Page 413
6.14 Permutation
......Page 414
6.16 Permutation Group
......Page 415
6.18 Cycle Index of the Pair Group
......Page 416
6.19 Equivalence Classes of Functions
......Page 417
6.22 Permutation Group
......Page 425
6.26.3. Composition Group
......Page 426
6.28 Highly Symmetric Graphs
......Page 427
Problem Set 6.1
......Page 430
7.2.1. Point Independence Number
......Page 434
7.4.2. Minimal edge Covering
......Page 435
7.6 Line-Core and Point-Core
......Page 436
7.8 1-Factorization
......Page 437
7.10 Arboricity
......Page 438
Problem Set 7.1
......Page 446
8.2 Orientation of a Graph
......Page 448
8.6 In-Degree and Out-Degree
......Page 449
8.11.1. Simple Digraphs......Page 450
8.11.4. Isomorphic Digraphs......Page 451
8.11.6. Regular Digraph......Page 452
8.12.3. Component and Fragments
......Page 453
8.14 Reachability
......Page 454
8.17.1. Spanning Arborescence
......Page 455
8.19 Hand Shaking Dilemma
......Page 456
8.21.3. Semi-circuit
......Page 457
8.24 Circuit Matrix of a Digraph
......Page 458
8.25 Adjacency Matrix of a Digraph
......Page 459
8.26. Nullity of a Matrix
......Page 475
Problem Set 8.1
......Page 481