Page 6 - Discrete Mathematics and Its Applications

Contents v

10 Graphs ............................................................ 641

10.1 Graphs and Graph Models .................................................... 641
10.2 Graph Terminology and Special Types of Graphs................................651
10.3 Representing Graphs and Graph Isomorphism .................................. 668
10.4 Connectivity ................................................................ 678
10.5 Euler and Hamilton Paths.....................................................693
10.6 Shortest-Path Problems.......................................................707
10.7 Planar Graphs ............................................................... 718
10.8 Graph Coloring..............................................................727
End-of-Chapter Material ..................................................... 735

11 Trees...............................................................745
11.1 Introduction to Trees ......................................................... 745
11.2 Applications of Trees.........................................................757
11.3 Tree Traversal ............................................................... 772
11.4 Spanning Trees .............................................................. 785
11.5 Minimum Spanning Trees .................................................... 797
End-of-Chapter Material ..................................................... 803

12 Boolean Algebra ................................................... 811
12.1 Boolean Functions ...........................................................811
12.2 Representing Boolean Functions .............................................. 819
12.3 Logic Gates ................................................................. 822
12.4 Minimization of Circuits ..................................................... 828
End-of-Chapter Material ..................................................... 843

13 Modeling Computation ........................................... 847

13.1 Languages and Grammars .................................................... 847
13.2 Finite-State Machines with Output.............................................858
13.3 Finite-State Machines with No Output ......................................... 865
13.4 Language Recognition ....................................................... 878
13.5 Turing Machines.............................................................888
End-of-Chapter Material ..................................................... 899

Appendixes ....................................................... A-1
1 Axioms for the Real Numbers and the Positive Integers ............................ 1
2 Exponential and Logarithmic Functions .......................................... 7
3 Pseudocode .................................................................. 11

Suggested Readings B-1
Answers to Odd-Numbered Exercises S-1
Photo Credits C-1
Index of Biographies I-1
Index I-2