Assignment 5 Solutions PDF

Preview

Summary

Zima Solutions A5...

Description

1. [5 marks] Give an example of a connected, weighted, undirected graph such that no matter at which vertex you start a DFS (depth first search) the resulting DFS-tree is not a MST (minimum spanning tree), regardless of how the adjacency lists are ordered. Justify correctness of your example.

Solution. No matter where you start DFS and independently on the order of adjacent vertices in the adjacency list, the DFS will have to enter one of the triangles through the vertex adjacent to the central edge. This means that the spanning DFS sub-tree for this triangle will have the weight of 11, while minimum weight sub-tree spanning this triangle has the weight of 2. 2. [7 marks] Let G be a directed acyclic graph. Design a linear time algorithm (Θ(|V | + |E |)) to decide if there is a directed path in G that goes through every vertex exactly once. Provide justification of the correctness and analyze running time complexity of your algorithm. Your algorithm has to have a running time in O(|V | + |E|). Solution. Run DFS to find a topological sort of the graph and test if that ordering is a directed path. If it is, then output the path, otherwise output FAIL. (Recall that we get a topological sort by ordering the vertices in decreasing order of finish time.) This does work correctly. If the algorithm outputs a path, then that is correct. For the other direction, suppose the graph has a directed path that goes through every vertex exactly once. Since the graph is acyclic, it has a topological sort. In a topological sort, the vertices must appear in the order of the directed path. So the topological sort is unique, and the algorithm will find it. 3. [6 marks] Prove that if the BFS and DFS spanning trees of a connected undirected graph G from the same start vertex s are equal to each other, then G is a tree. Solution. Assume for contradiction that G is a connected graph that is not a tree and that there is a vertex s such that the BFS tree T and the DFS tree T ′ are equal to each other. Since G is not a tree, there must be some cycle in G and some non-tree edge (u, v) connecting u to one of its ancestors v in the DFS tree T ′ . But then u cannot be a descendant of v in the BFS tree T unless it is its child (in which case (u, v) is a tree edge) so T 6= T ′ . 4. [10 marks] Suppose you are given a connected undirected weighted graph G with a particular vertex s designated as the source. It is also given to you that weight of every edge in this graph is equal to 1 or 2. You need to find the shortest path from source s to every other vertex in the graph. This could be done using Dijkstra’s algorithm but you are told that you must solve this problem using a breadth-first search strategy. Design a linear time algorithm 1

(Θ(|V | + |E |)) that will solve your problem. Show that running time of your modifications is O(|V | + |E |). Hint: You may modify the input graph (as long as you still get the correct shortest path distances). Solution. There are multiple valid solutions... Simplest one is to modify graph by replacing every edge (u, v) with weight 2 by two edges with weight 1. New graph G′ = (V ′ , E ′ ) has |V ′ | ≤ |V |+|E| and |E ′ | ≤ 2|E |. Time to construct this graph in adjacency list representation is Θ(|V ′ | + |E ′ |). BFS that starts at source vertex in G′ will produce the length of shortest path from the source to every vertex in graph G′ . The cost of BFS is in Θ(|V ′ | + |E ′ |). Since |V | + |E| ≤ |V ′ | + |E ′ | ≤ |V | + 3|E| < 3(|V | + |E |) the running time is in Θ(|V | + |E |). 5. [10 marks] Prove or disprove each of the following statements, where in each case G = (V, E) is a connected undirected weighted graph with n vertices and m edges. (a) If G has m ≥ n edges and a unique heaviest edge e, then e is not part of any minimum spanning tree of G. Solution.

False. Consider the graph 100

that has 4 vertices and 4 edges, three of which of weight 1 and one of which has weight 100. The unique heaviest edge of weight 100 must be included in any spanning tree of the graph, so it is also in the minimum spanning tree. (b) If G has m ≥ n edges and a unique lightest edge e, then e is part of every minimum spanning tree of G. Solution. True. The proof is very similar to that of the Cut Property in lecture notes. Assume for contradiction that there is a MST T of G that does not include e. Then if we add the edge e to T , we create a cycle in the graph and we can remove any other edge e′ 6= e in the cycle to obtain another spanning tree T ′ of G. But the resulting tree T ′ has smaller weight than T , contradicting the fact that T was a MST of G. (c) If e is a maximal weight edge of a cycle of G, then there is a minimum spanning tree of G that does not include e. Solution. True. Let T = (V, E′ ) be a MST of G that includes e. Let X = E ′ \ {e} be the set of edges in T except for e. Then X is part of a MST of G and there must be a set S ⊆ V (that includes exactly one of the two end vertices of e) for which X has no edges that crosses the cut (S, V \ S). The edge e crosses the cut, but since e is part of a cycle, there must be another edge e′ 6= e in the cycle that in the minimum-weight edge crossing the cut. (The edge e cannot be the unique minimal weight edge crossing the cut since it has maximal weight among the edges in the cycle.) By the Cut Property Lemma, the tree T ′ with edges X ∪ {e′ } is a MST of G that does not contain the edge e. 2

(d) Kruskal’s algorithm returns a minimum spanning tree of G even when the edge weights can be either positive or negative. Solution. True. The analysis of Kruskal’s algorithm in the lecture notes for does not assume anything about the edge weights, so it works with both positive and negative weights. If we want to be extra careful and assume that this analysis only works for non-negative weights, then for any graph G with some negative edge weights, let −γ denote the minimum weight of any edge of G. Let G′ = (V, E) be the weighted graph with weight function w′ : E → R defined by w′ (e) = w(e) + γ. Then the graph G′ has non-negative edge weights and Prim’s algorithm computes a MST T ′ of G′ . The same tree is also a MST of G since the for every tree T , costw (T ) = costw′ (T ) − (n − 1)γ . 6. [12 marks] Given a directed graph with positive edge lengths and a specified vertex v in the graph, the “all-pairs v-constrained shortest path problem” is the problem of computing for each pair of vertices i and j the length of the shortest path from i to j that goes through the vertex v. If no such path exists, the answer is ∞. Describe an algorithm that takes a graph G = (V, E) and vertex v as input parameters and computes values L(i, j) that represent the length of v-constrained shortest path from i to j for all 1 ≤ i, j ≤ |V |, i 6= v, j 6= v. Prove your algorithm correct. Your algorithm should have a running time in O(|V |2 ). Solution. By Bellman optimality principle (or by the common sense), any v constrained shortest path from i to j consists of two “legs”: 1) shortest path from i to v, and 2) shortest path from v to j . To compute 2) just run Dijkstra’s algorithm on graph G with source v, and to compute 1) run the same Dijkstra’s algorithm on transpose of graph G with source v. Combining the results of two runs gives desired answer. APvCSP(G, v) { // compute the length of shortest path from v to every other vertex D1 = Dijksta(G, v); // in O(|V|^2) // compute transpose of the given graph GG = Transpose(G); // is Theta(|V|+|E|) in O(|V|^2) // compute the length of shortest path from v to every other vertex D2 = Dijkstra(GG, v); // in O(|V|^2) // combine the results at the cost of O(|V|^2) for i in V\{v} do for j in V\{v} do L[i,j] = D2[i] + D1[j]; od od return L } Complexity if this algorithm is trivially in O(|V |2 ).

3...