CONTENTS ix 7.8 Chebyshev's Inequality,Law of Large Numbers 135 Solved Problems 136 Supplementary Problems 149 CHAPTER 8 Graph Theory 154 8.1 Introduction,Data Structures 154 8.2 Graphs and Multigraphs 156 8.3 Subgraphs,Isomorphic and Homeomorphic Graphs 158 8.4 Paths,Connectivity 159 8.5 Traversable and Eulerian Graphs,Bridges of Konigsberg 160 8.6 Labeled and Weighted Graphs 162 8.7 Complete,Regular,and Bipartite Graphs 162 8.8 Tree Graphs 164 8.9 Planar Graphs 166 8.10 Graph Colorings 168 8.11 Representing Graphs in Computer Memory 171 8.12 Graph Algorithms 173 8.13 Traveling-Salesman Problem 176 Solved Problems 178 Supplementary Problems 191 CHAPTER 9 Directed Graphs 201 9.1 Introduction 201 9.2 Directed Graphs 201 9.3 Basic Definitions 202 9.4 Rooted Trees 204 9.5 Sequential Representation of Directed Graphs 206 9.6 Warshall's Algorithm,Shortest Paths 209 9.7 Linked Representation of Directed Graphs 211 9.8 Graph Algorithms:Depth-First and Breadth-First Searches 213 9.9 Directed Cycle-Free Graphs,Topological Sort 216 9.10 Pruning Algorithm for Shortest Path 218 Solved Problems 221 Supplementary Problems 228 CHAPTER 10 Binary Trees 235 10.1 Introduction 235 10.2 Binary Trees 235 10.3 Complete and Extended Binary Trees 237 10.4 Representing Binary Trees in Memory 239 10.5 Traversing Binary Trees 240 10.6 Binary Search Trees 242 10.7 Priority Queues,Heaps 244 10.8 Path Lengths,Huffman's Algorithm 248 10.9 General(Ordered Rooted)Trees Revisited 251 Solved Problems 252 Supplementary Problems 259CONTENTS ix 7.8 Chebyshev’s Inequality, Law of Large Numbers 135 Solved Problems 136 Supplementary Problems 149 CHAPTER 8 Graph Theory 154 8.1 Introduction, Data Structures 154 8.2 Graphs and Multigraphs 156 8.3 Subgraphs, Isomorphic and Homeomorphic Graphs 158 8.4 Paths, Connectivity 159 8.5 Traversable and Eulerian Graphs, Bridges of Königsberg 160 8.6 Labeled and Weighted Graphs 162 8.7 Complete, Regular, and Bipartite Graphs 162 8.8 Tree Graphs 164 8.9 Planar Graphs 166 8.10 Graph Colorings 168 8.11 Representing Graphs in Computer Memory 171 8.12 Graph Algorithms 173 8.13 Traveling-Salesman Problem 176 Solved Problems 178 Supplementary Problems 191 CHAPTER 9 Directed Graphs 201 9.1 Introduction 201 9.2 Directed Graphs 201 9.3 Basic Definitions 202 9.4 Rooted Trees 204 9.5 Sequential Representation of Directed Graphs 206 9.6 Warshall’s Algorithm, Shortest Paths 209 9.7 Linked Representation of Directed Graphs 211 9.8 Graph Algorithms: Depth-First and Breadth-First Searches 213 9.9 Directed Cycle-Free Graphs, Topological Sort 216 9.10 Pruning Algorithm for Shortest Path 218 Solved Problems 221 Supplementary Problems 228 CHAPTER 10 Binary Trees 235 10.1 Introduction 235 10.2 Binary Trees 235 10.3 Complete and Extended Binary Trees 237 10.4 Representing Binary Trees in Memory 239 10.5 Traversing Binary Trees 240 10.6 Binary Search Trees 242 10.7 Priority Queues, Heaps 244 10.8 Path Lengths, Huffman’s Algorithm 248 10.9 General (Ordered Rooted) Trees Revisited 251 Solved Problems 252 Supplementary Problems 259