xiv
Contents
6.12 Rooted Trees 378
6.12.1 Binary Trees 380
6.12.2 Binary Search Trees 382
6.12.3 Tree Traversals 385
6.12.4 Application: Decision Trees 387
6.13 Exercises 389
6.14 Directed Graphs 392
6.14.1 Basic Definitions 393
6.14.2 Directed Trails, Paths, Circuits, and Cycles 394
6.14.3 Directed Graph Isomorphism 394
6.15 Application: Scheduling a Meeting Facility 394
6.15.1 WAITFOR Graphs 396
6.16 Finding a Cycle in a Directed Graph 397
6.16.1 Directed Cycle Detection Algorithm 397
6.16.2 Correctness of Directed Cycle Detection 398
6.17 Priority in Scheduling 399
6.171 Algorithm for Topological Sort 400
6.172 Correctness of Topological Sort Algorithm 401
6.18 Connectivity in Directed Graphs 402
6.18.1 Strongly Connected Directed Graphs 402
6.18.2 Application: Designing One-Way Street Grids 404
6.19 Eulerian Circuits in Directed Graphs 405
6.20 Exercises 406
6.21 Chapter Review 409
6.21.1 Summary 409
6.21.2 Starting to Review 411
6.21.3 Review Questions 413
6.21.4 Using Discrete Mathematics in Computer Science 416
CHAPTER 7
Counting and Combinatorics
421
7.1 Traveling Salesperson's Problem 421