Cs 3510 hw7 sol - Dana Randall PDF

Preview

Summary

Dana Randall...

Description

CS 3510-B Homework 7 Solutions You must submit this homework on Gradescope. You can work together on homeworks, but you must write up solutions by yourself. Getting solutions from the web is forbidden. Exams and homework are similar, so it is in your best interest to try to solve problems by yourself. 1. For the following subproblems, consider the edge-weighted undirected graph G below.

(a) Use Kruskal’s algorithm to find a minimum spanning tree of G. Draw the minimum spanning tree below and give its total weight. Solution. There are two minimum spanning trees of G with weight 37.

(b) Run Dijkstra’s algorithm from the source vertex a and give the lengths of the shortest paths from a to all other vertices. Solution. Running Dijkstra’s algorithm from the source vertex a, the final shortest path distances are given in the bottom row of the following table. step vertex a b c d e f g h i 0 a 0 ∞ ∞ ∞ ∞ ∞ ∞ ∞ ∞ 1 b 0 4 ∞ ∞ ∞ ∞ ∞ 8 ∞ 2 h 0 4 12 ∞ ∞ ∞ ∞ 8 ∞ 3 g 0 4 12 ∞ ∞ ∞ 9 8 15 4 f 0 4 12 ∞ ∞ 11 9 8 15 5 c 0 4 12 25 21 11 9 8 15 6 i 0 4 12 19 21 11 9 8 14 7 d 0 4 12 19 21 11 9 8 14 8 e 0 4 12 19 21 11 9 8 14 1

2. Give an algorithm that finds shortest paths from a given node in a directed graph that contains exactly one negative weighted edge. Assume that the graph does not contain any negative weight cycles. The running time should be the same as Dijkstra’s algorithm. Solution. Let s denote the source vertex and let t denote an arbitrary target vertex. A shortest path from s to t either passes through the negative weight edge e = (u, v) or it does not. Therefore, we consider both cases separately and take the minimum. This decision allows us to easily reconstruct the shortest paths. Let G′ denote the graph without edge e. Run Dijkstra’s algorithm on G′ starting from s to obtain shortest paths with lengths dist’(s, x) for all vertices x ∈ V . Next, run Dijkstra’s algorithm on G′ from v to obtain shortest paths with length dist’(v, x) for all x ∈ V . Our claim is that in the original graph the shortest paths from s have values dist(s, x) = min{dist’(s, x), dist’(s, u) + weight(u, v) + dist’(v, x)}. Since there are no negative weight cycles, a shortest path passes through e at most once. This completes the proof of correctness, as it covers all possible cases for paths from s to x. The running time of this algorithm is the same as Dijkstra’s since we ran Dijkstra’s algorithm twice on a subgraph of G.

2

3. A developing country desires to build a network of roads so that a route exists between the capital city and a number of villages. We are given an undirected graph G = (V, E) where n = |V | and m = |E |. The weight of each edge {u, v} ∈ E is the cost of building a road between u and v . (a) Give an algorithm that finds a satisfactory network of roads with the least total cost whose running time is O((n + m) log(n)). Solution. Since the graph is undirected, the condition that a route exists between the capital city and all villages implies that the graph is connected. A network that is connected and of minimum cost is a minimum spanning tree, so we can use Kruskal’s algorithm since its running time is O(m log(n)).

(b) How would the cheapest network of roads change if the country moves the capital to one of the villages? Solution. If the capital city is moved to a village and the old capital is now considered a village, the connectivity requirement of the graph is unchanged. Therefore, the cheapest connected network retains the same value.

3

(c) The bottleneck in a network of roads is the edge that is the most expensive to build. The bottleneck of a graph is the smallest of all the bottlenecks that exist for each possible satisfactory network of roads that could be built. (In other words, we examine each satisfactory network that can be built, for each satisfactory network we consider the edge with the most weight, and then we take the minimum over all such networks.) Give an algorithm that finds the bottleneck of a graph. The running time should be O((n + m) log(n)). Solution. The goal is to construct a connected graph such that the maximum edge weights are minimized. We can modify Kruskal’s algorithm as follows. First, sort the edges by weight. Next, iterative over the edges in non-decreasing order and add each edge to the network until the graph is fully connected. Once this occurs, we have identified the weight of a bottleneck edge of the graph. The proof of correctness follows from a greedy argument since the we iterate over the edges in non-decreasing order and maximize the connectivity of the subgraph at each step. Similar to the running time of Kruskal’s algorithm, this procedure takes O(m log(n)) time. Note that this argument also implies that the heaviest edges in a minimum spanning tree obtained via Kruskal’s algorithm are bottleneck edges of the graph.

4

4. Consider an edge-weighted undirected graph G = (V, E) and a particular edge e. (a) We wish to find a spanning tree T of G such that (1) T includes the edge e, and (2) T has minimal weight over all spanning trees containing e. Can this problem be solved by first picking e and then running Prim’s algorithm to complete the spanning tree? What about Kruskal’s algorithm? Justify your answers. Solution. In both cases, picking e = {u, v} and then running Prim’s algorithm or Kruskal’s will obtain such a tree. Since we are restricting ourselves to consider spanning trees that include e, vertices u and v are always be connected via e since there exist a unique path between any pair of vertices in a spanning tree. Therefore, we can think of contracting u and v into a single node x to obtain a new graph G′ without any selected edges. Next, we can run Prim’s or Kruskal’s algorithm on G′ to obtain a MST of G′ and then expand x back into u and v to obtain a desired spanning tree for G.

5

(b) Let G be a connected undirected graph with the property that every edge has a different weight. Prove that there is only one minimum spanning tree for G. (Hint: assume that there are two and examine the lightest edge that is in one tree but not the other to arrive at a contradiction.) Solution. Suppose T1 and T2 are different minimum spanning trees of G. Let e be the minimum weight edge in T1 and not in T2 . Let c denote the cycle in the graph T2 ∪ {e}. All edges have different weights, so it must be that e is the heaviest edge in c, for otherwise we could remove a different edge on the cycle f ∈ c \ {e} to obtain a lighter minimum spanning tree T2 ∪{e}\{f }, which is a contradiction. We also know that there must exist an edge f ∈ c that is not in T1 . Our earlier argument asserts that weight(f ) < weight(e) since e is the heaviest edge in c. Considering the graph T1 ∪ {f } \ {e} yields a spanning tree that is lighter than T1 , which is a contradiction since we assumed T1 is a minimums spanning tree. Therefore, it cannot be that T1 and T2 have different values.

6

5. Let T be an MST of a graph G. Given a connected subgraph H of G, show that T ∩ H is contained in some MST of H. (A subgraph H = (VH , EH ) of a graph G = (VG , EG ) has VH ⊆ VG and EH ⊆ EG .) Solution. Suppose for contradiction that the claim is not true. Then T ∩ H is nonempty and by the cut lemma there exists an edge e ∈ T ∩ H across some cut (S, VH \ S) of H such that there exists another edge e′ across the cut that is lighter than e. Augmenting the cut (S, VH \ S) 7→ (S, V ) to G means that e′ can be used to replace e in T to obtain a lighter spanning tree, contradicting the assumption that T is an MST. Therefore, T ∩ H is a subset of some MST of H .

7...