Graph Algorithms and Disjoint Sets_Assignment 4

This assignment covers Chapters 22-25 (graph algorithms) and 21 (disjoint sets) of the text [100 marks total].
1. Babyfaces vs. Heels. [10 marks total] There are two types of professional wrestlers: “babyfaces” (the good guys) and “heels” (the bad guys). Between any pair of wrestlers there may or may not be a rivalry. Suppose there are n wrestlers and we have a list of r pairs of wrestlers for which there are rivalries.
(a) Give an algorithm that determines whether it is possible to designate some of the wrestlers as babyfaces and the remainder as heels such that each rivalry is between a babyface and a heel. If it is possible to perform such a designation, your algorithm should produce it. (b) What is the worst-case run time of your algorithm?
2. DFS of a Directed Graph. [10 marks total] Given the following directed graph, traverse the graph by depth-first search (DFS) starting at vertex a and visiting vertices in alphabetical order. • Label each vertex with its discovery and finish time. • Construct the corresponding DFS forest in the standard form. • Classify each edge as a tree (T), forward (F), back (B), or cross (C) edge.
ab
cd e
f
g
3. Connected Components. [10 marks total] Show how to modify depth-first search (DFS) of an undirected graph G to identify the connected components of G, and that the depth-first forest contains as many trees as G has connected components. More precisely, show how to modify DFS so that it assigns to each vertex v and integer label between 1 and k, where k is the number of connected components of G, such that the labels of two vertices u and v are equal if and only if u and v are in the same connected component.
4. Minimum Spanning Tree (MST) Algorithms. [20 marks total]
(a) Apply Prim’s algorithm to the following graph. Include in the priority queue all the vertices not already in the tree.
6. B Averaging down There are qA1 identical vessels, one of them with Z pints of water and the others empty. You are allowed to perform the following operation: take two of the vessels and split the total amount of water in them equally between them. The object is to achieve a minimum amount of water in the vessel containing all the water in the initial set up by a sequence of such operations. What is the best way to do this?
7. Rumor spreading There are q people, each in possession of a different rumor. They want to share all the rumors with each other by sending electronic messages. Assume that a sender includes all the rumors he or she knows at the time the message is sent and that a message may only have one addressee. Design a greedy algorithm that always yields the minimum number of messages they need to send to guarantee that everyone of them gets all the rumors. 8. Bachet’s problem of weights Findanoptimalsetof qweights{z1z2===zq} so that it would be possible to weigh on a balance scale any integer load in the largest possible range from 1 to Z, provided
a.B weights can be put only on the free cup of the scale. b.I weights can be put on both cups of the scale. 9. a. Apply Prim’s algorithm to the following graph. Include in the priority queue all the vertices not already in the tree.
c
a b
d
5
4
7 6 e 23 45
b. Apply Prim’s algorithm to the following graph. Include in the priority queue only the fringe vertices (the vertices not in the current tree which
2
1
(b) Now, apply Prim’s algorithm to the following graph. Include in the priority queue only the fringe vertices (the vertices not in the current tree which are adjacent to at least one tree vertex). are adjacent to at least one tree vertex).
i
e f
j
9
5
h
d
g
c
ba
lk
3
6
8
6
5
4
3 6 3
2 1 2
5 4
75
43
10. The notion of a minimum spanning tree is applicable to a connected weighted graph. Do we have to check a graph’s connectivity before applying Prim’s algorithm or can the algorithm do it by itself?
11. Does Prim’s algorithm always work correctly on graphs with negative edge weights?
12. Let W be a minimum spanning tree of graph J obtained by Prim’s algorithm. Let Jqhz be a graph obtained by adding to J a new vertex and some edges, with weights, connecting the new vertex to some vertices in J. Can we construct a minimum spanning tree ofJqhz by adding one of the new edges to W? If you answer yes, explain how; if you answer no, explain why not.
13. a. How can we use Prim’s algorithm to find a spanning tree of a connected graph with no weights on its edges?
b. Is it a good algorithm for this problem? 14. B Prove that any weighted connected graph with distinct weights has exactly one minimum spanning tree.
15. Outline an efficient algorithm for changing an element’s value in a minheap. What is the time efficiency of your algorithm?
3
(c) Apply Kruskal’s algorithms to find a MST in the graph below and also to the graph in part (b). Exercises 9.2 1. Apply Kruskal’s algorithm to find a minimum spanning tree of the following graphs. a.
a
b
d
1 c
e
5
6 2
6
3 4
b.
i
e f
j
9
5
h
d
g
c
ba
lk
3
6
8
6
5
4
3 6 3
2 1 2
5 4
75
43
2. Indicate whether the following statements are true or false:
a. If h is a minimum-weight edge in a connected weighted graph, it must be among edges of at least one minimum spanning tree of the graph.
b. If h is a minimum-weight edge in a connected weighted graph, it must be among edges of each minimum spanning tree of the graph.
c. If edge weights of a connected weighted graph are all distinct, the graph must have exactly one minimum spanning tree.
d. If edge weights of a connected weighted graph are not all distinct, the graph must have more than one minimum spanning tree. 3. What changes, if any, need to be made in algorithm Kruskal to make it find a minimum spanning forest for an arbitrary graph? (A minimum spanning forest is a forest whose trees are minimum spanning trees of the graph’s connected components.) 4. Does Kruskal’s algorithm work correctly on graphs that have negative edge weights?
15
5. Second-best Minimum Spanning Tree (MST). [15 marks] Let G = (V,E) be an undirected, connected graph whose weight function is w : E →R, and suppowe that |E|≥|V| and all edge weights are distinct. We define the second-best minimum spanning tree as follows. Let T be the set of all spanning trees of G, and let T0 be a MST of G. Then a second-best minimum spanning tree is a spanning tree T such that w(T) = minT00∈(T−T0){w(T00)}. (a) Show that the MST is unique, but that the second-best MST need not be unique. (b) Let T be the MST of G. Prove that G contains edges (u,v) ∈ T and (x,y) 6∈ T such that T −{(u,v)}∪{(x,y)} is a second-best MST of G. (c) Given an efficient algorithm to compute the second-best MST of G.
6. Variations of Dijkstra’s Algorithm. [15 marks] Explain what adjustments if any need to be made in Dijkstras algorithm and/or in an underlying graph to solve the following problems.
(a) Solve the single-source shortest-paths problem for directed weighted graphs. (b) Find a shortest path between two given vertices of a weighted graph or digraph. (This variation is called the single-pair shortest-path problem.) (c) Find the shortest paths to a given vertex from each other vertex of a weighted graph or digraph. (This variation is called the single-destination shortest-paths problem.)
7. Dijkstra’s Algorithm. [10 marks] Trace the Dijkstra’s algorithm on the graph in Question 4(b) with vertex a as the source.
8. Disjoint Sets. [10 marks] Professor Gump suggests that it might be possible to keep just one pointer in each set object, rather than two (head and tail), while keeping the number of pointers in each list element at two. Show that
2
the professor’s suggestion is well-founded by describing how to represent each set by a linked list such that each operation Make-Set, Union, and Find-Set has the same running time as the operations using the standard linked list representation of disjoint sets. Describe also how the operations work. Your scheme should allow for the weighted-union heuristic, with the same effect.