Contents
xiii
CHAPTER 6
Graph Theory
331
6.1 Introduction to Graph Theory 331
6.1.1 Definitions 334
6.1.2 Subgraphs 336
6.2 The Handshaking Problem 338
6.3 Paths and Cycles 340
6.3.1 Hamiltonian Cycles 341
6.4 Graph Isomorphism 345
6.5 Representation of Graphs 346
6.5.1 Adjacency Matrix 346
6.5.2 Adjacency Lists 347
6.6 Exercises 348
6.7 Connected Graphs 352
6.71 The Relation CONN 352
6.7.2 Depth First Search 354
6.7.3 Complexity of Dfs 357
6.74 Breadth First Search 357
6.7.5 Finding Connected Components 359
6.8 The K6nigsberg Bridge Problem 361
6.8.1 Graph Tracing 365
6.9 Exercises 367
6.10 Trees 370
6.10.1 Definition of Trees 371
6.10.2 Characterization of Trees 372
6.11 Spanning Trees 374
6.11.1 Kruskal's Algorithm 374
6.11.2 Correctness of Kruskal's Algorithm 375
6.11.3 Kruskal's Algorithm for Weighted Graphs 376
6.11.4 Correctness of Kruskal's Weighted Graph Algorithm 378