392 CHAPTER 6 Graph Theory
- Design a minimum depth decision tree to solve each of the following problems:
(a) Take the water in an eight-gallon jug, and divide it into two four-gallon portions
using a three-gallon jug and a five-gallon jug that initially are empty.
(b) Take the water in a six-gallon jug, and end with two gallons in a four-gallon jug
using a four-gallon jug and a three-gallon jug that initially are empty. - Draw a minimal depth decision tree that represents sorting four elements from a lin-
early ordered set. Only five levels are required. - Let G = (V, E) be a connected graph. The distance between two vertices v, w E V,
denoted D(v, w), is the length of a shortest path joining v to w. A vertex u of G is
in the center of G if maxvEV(G) d(u, v) is as small as possible. Prove that a tree has
either one or two vertices in its center. - A binary tree is said to be complete if all its leaves occur at the lowest level. For a
complete binary tree of height h, determine the number of vertices at level i where
I < i < h. Prove that the number of leaves is one more than the number of internal
vertices.
Definition 1. A heap of height h is an arrangement of numbers at the nodes of a binary
tree such that the following hold:(a) All the leaves are either at level h or at level h - 1.
(b) There are 2i vertices at level h for h = 0, 1 .... h - 1.
(c) All the leaves at level h are at the leftmost possible positions.
(d) The number at any internal node is larger than the number at either of its two
children.- Given a heap, what can you say about the number at its root? By removing the num-
ber at the root of a heap and replacing it with the number in the rightmost leaf, the
property of being a heap is destroyed. Devise an algorithm to restore the property of
being a heap. Use this algorithm to devise a sorting algorithm, and then determine the
complexity of this sorting algorithm.
Directed Graphs
The detection of a bottleneck in allocating resources to computer programs, the schedul-
ing of jobs that depend on the completion of other jobs, and the design of one-way street
grids are all problems that are modeled by graphs. An important facet in these problems,
however, is not reflected in the structure of a graph. Often, a natural notion of direction is
associated with the connection between vertices. For instance, one can associate the ver-
tices of a graph with the intersections of streets and the edges with pairs of vertices that
indicate the way that traffic is allowed to flow on the streets in a section of a town with only
one-way streets. We first introduce directed graphs, which deal with graphs that have a di-
rection associated with each edge. We then use this terminology to model deadlock in an
operating system. An analogue of a depth first search in an undirected graph will be used
with directed graphs to solve scheduling problems for sets of prioritized events. A distinc-
tion between the notion of connectedness for directed graphs and for undirected graphs will
be explored. Finally, an analogue of Euler's theorem will be presented for directed graphs.