d. False (see, for example, the graph of Problem 1a).
3. Since the number of edges in a minimum spanning forest of a graph with
||vertices and ||connectedcomponentsisequalto||−||(this for-
4. Both algorithms work correctly for graphs with negative edge weights.
One way of showing this is to add to all the weights of a graph with
5. Replace each weight ( )by −( )and apply any minimum spanning
tree algorithm that works on graphs with arbitrary weights (e.g., Prim’s
or Kruskal’s algorithm) to the graph with the new weights.
6. Algorithm Kruskal()
//Kruskal’s algorithm with explicit disjoint-subsets operations
//Input: A weighted connected graph =h i
//Output: , the set of edges composing a minimum spanning tree of
7. Let us prove by induction that each of the forests =0 ||−1of
Kruskal’s algorithm is a part (i.e., a subgraph) of some minimum span-
ning tree. (This immediately implies, of course, that the last forest in the
sequence, ||−1is a minimum spanning tree itself. Indeed, it contains
made up of ||single-vertex trees and therefore must be a subgraph of
any spanning tree of the graph. For the inductive step, let us assume that
−1is a subgraph of some minimum spanning tree . We need to prove
that generated from −1by Kruskal’s algorithm, is also a part of a
minimum spanning tree. We prove this by contradiction by assuming that
no minimum spanning tree of the graph can contain .Let=( )
be the minimum weight edge added by Kruskal’s algorithm to forest −1
8. In the union-by-size version of quick-union, each vertex starts at depth
0 of its own tree. The depth of a vertex increases by 1 when the tree
it is in is attached to a tree with at least as many nodes during a union
9. n/a
11. The minimum Steiner tree that solves the problem is shown below. (The
other solution can be obtained by rotating the figure 90◦.)
ab
12. n/a
23
Exercises 9.3
1. Explain what adjustments if any need to be made in Dijkstra’s algorithm
and/or in an underlying graph to solve the following problems.
a. Solve the single-source shortest-paths problem for directed weighted
graphs.
2. Solve the following instances of the single-source shortest-paths problem
with vertex as the source:
a.
a
b
d
4c
e
3
6
25
3. Give a counterexample that shows that Dijkstra’s algorithm may not work
for a weighted connected graph with negative weights.
24
4. Let be a tree constructed by Dijkstra’s algorithm in the process of
solving the single-source shortest-path problem for a weighted connected
graph .
6. BProve the correctness of Dijkstra’s algorithm for graphs with positive
weights.
7. Design a linear-time algorithm for solving the single-source shortest-paths
problem for dags (directed acyclic graphs) represented by their adjacency
lists.
10. Revisit Problem 6 in Exercises 1.3 about determining the best route for
a subway passenger to take from one designated station to another in a
25
Hints to Exercises 9.3
1. One of the questions requires no changes in either the algorithm or the
graph; the others require simple adjustments.
5. Simplify the pseudocode given in the section by implementing the priority
queue as an unordered array and ignoring the parental labeling of vertices.
6. Prove it by induction on the number of vertices included in the tree con-
structed by the algorithm.
26
Solutions to Exercises 9.3
1. a. It will suffice to take into account edge directions in processing adjacent
vertices.
b. Start the algorithm at one of the given vertices and stop it as soon
as the other vertex is added to the tree.
2. a.
a
b
d
4c
e
3
74
6
25
Tree vertices Remaining vertices
27
b.
ba
3
6
5
43
Tree vertices Fringe vertices Shortest paths from
a(-,0) b(a,3) c(a,5) d(a,4) to :−of length 3
b(a,3) c(a,5) d(a,4) e(b,3+3) f(b,3+6) to :−of length 4
d(a,4) c(a,5) e(d,4+1) f(a,9) h(d,4+5) to :−of length 5
3. Consider, for example, the graph
a
c
b
3
2
– 2
it includes all the vertices of the graph. Hence, it’s a spanning tree.
b. False. Here is a simple counterexample:
5. Algorithm SimpleDijkstra([0 −10 −1])
//Input: A matrix of nonnegative edge weights and
// integer between 0 and −1indicating the source
//Output: An array [0 −1] of the shortest path lengths
6. We will prove by induction on the number of vertices in tree con–
structed by Dijkstra’s algorithm that this tree contains closest vertices
to source (including the source itself), for each of which the tree path
from to is a shortest path of length For =1the assertion is
7. Algorithm DagShortestPaths( )
//Solves the single-source shortest paths problem for a dag
//Input: A weighted dag =hiand its vertex
//Output: The length of a shortest path from to and
8. Create a digraph by connecting numbers on adjacent levels of the triangle
that can be components of a sum from the apex to the base. As a weight
9. a. Take the two balls representing the two singled out vertices in two
hands and stretch the model to get the shortest path in question as a
straight line between the two ball-vertices.
30
Exercises 9.4
1. a. Construct a Huffmancodeforthefollowingdata:
2. For data transmission purposes, it is often desirable to have a code with
a minimum variance of the codeword lengths (among codes of the same
average length). Compute the average and variance of the codeword
length in two Huffman codes that result from a different tie breaking
3. What is the maximal length of a codeword possible in a Huffman encoding
of an alphabet of characters?
4. a. Write pseudocode of the Huffman tree construction algorithm.
6. Given a Huffman coding tree, which algorithm would you use to get the
codewords for all the characters? What is its time-efficiency class as a
function of the alphabet’s size?
31