Discrete Mathematics for Computer Science

Spanning Trees 377 Kruskal's algorithm to find a spanning tree can be viewed as the special case of finding an MCST in a graph w ...

378 CHAPTER 6 Graph Theory 6.11.4 Correctness of Kruskal's Weighted Graph Algorithm Since the order in which the edges are consi ...

Rooted Trees 379 rection, a drawing of a rooted tree normally has the root vertex at the top and the remainder of the tree displ ...

380 CHAPTER 6 Graph Theory parent-child ancestor siblings Descendantt, Figure 6.40 Relationships between vertices. In discussing ...

Rooted Trees 381 Of special interest in computer science is the family of rooted trees in which each vertex has at most two chil ...

382 CHAPTER^6 Graph Theory 6.12.2 Binary Search Trees In addition to directing the edges away from the root in a binary tree, we ...

Rooted Trees 383 INPUT: Binary search tree T with root R and an element item of the type stored at the vertices of T OUTPUT: TRU ...

384 CHAPTER 6 Graph Theory The efficiency of searching a binary search tree depends on the form of the tree. In Figure 6.47, we ...

Rooted Trees 385 In general, if we suppose a binary search tree is built from a list of n randomly ordered elements. The first e ...

386 CHAPTER 6 Graph Theory VERTEX LABEL LISTINGS r left child /• * right child T 2 PREORDER List the label at the root vertex r ...

Rooted Trees 387 To carry out a preorder or a postorder listing, follow the same trail alongside the tree. For a preorder listin ...

388 CHAPTER 6 Graph Theory a bC a.-b C cb~ b:c a b:c a<b a< b b<a c <a b<c ,<c ~ ",,<, a~c°/b a/•b: cb [ -• ...

Exercises 389 (b) log 2 (n!) = 1og 2 (n) + log 2 (n - 1) + + log 2 (n/2) + 1og 2 (n/2 - 1) + + log 2 (4) + log 2 (3) + log 2 (2) ...

390 CHAPTER 6 Graph Theory Prove that a cycle and the complement of any spanning tree must have at least one edge in common. Le ...

Exercises 391 (b) Is the MCST in graph H unique? If not, find all examples. Find an MCST in the graph if (3, 4) and (2, 5) must ...

392 CHAPTER 6 Graph Theory Design a minimum depth decision tree to solve each of the following problems: (a) Take the water in ...

Directed Graphs 393 6.14.1 Basic Definitions To understand the differences between directed and undirected graphs, we must suppl ...

394 CHAPTER 6 Graph Theory 6.14.2 Directed Trails, Paths, Circuits, and Cycles The definitions for a directed trail, a directed ...

Application: Scheduling a Meeting Facility 395 would like to begin its meeting at the same time the first organization is comple ...

396 CHAPTER 6 Graph Theory 6.15.1 WAITFOR Graphs To model the general situation of handling the request for and the allocation o ...