Single Source Shortest Path
1.1 Exercise
(10 points)
We would like solve, as eciently as possible, the single source shortest paths problem in each of the following graphs. (Recall that in this problem, we must nd a shortest path from a designated source vertex to every vertex in the graph.) For each graph, state which algorithm (from among those we have studied in class and section) would be best to use, and give its running time. If you don’t know the name of the algorithm, give a brief description of it. If the running time depends on which data structures are used in the implementation, choose an arbitrary data structure.
Copyright By PowCoder代写 加微信 powcoder
a) A weighted directed acyclic graph.
b) A weighted directed graph where all edge weights are non-negative;
the graph contains a directed cycle.
c) A weighted directed graph in which some, but not all, of the edges have negative weights; the graph contains a directed cycle.
1.2 Exercise
(20 points)
We are given a directed graph G = (V, E) on which each edge (u, v) 2
2 E has an associated value r(u,v), which is a real number in the range 1
0 r(u, v) 1 that represents the reliability of a communication channel from vertex u to vertex v. We interpret r(u, v) as the probability that the channel from u to v will not fail, and we assume that these probabilities are independent. Give an ecient algorithm to nd the most reliable path between two given vertices.
1.3 Exercise
(20 points)
You are in charge of planning cycling vacations for a travel agent. You have a map of n cities connected by direct bike routes. A bike route connecting cities v and u has distance d(v, u). Additionally, it costs c(v) to stay in city v for a single night. A customer will provide you with the following data:
{ A starting city s.
{ A destination city t.
{ A trip length m.
{ A daily maximum biking distance u(k), where k 2 [1, m].
Your job is to plan a tour that takes exactly m days, such that the customer does not stay in the same city two consecutive nights and does not bike more than u(k) on day k. Your customer can bike through several cities on a given day, i.e. there doesn’t have to be a direct route between the cities you assign on day k and day k + 1. You also want to minimize the total cost of staying at the cities on your tour.
Give an O n2(n + m) time algorithm to produce an m-city tour (s = v0,
v1,…,t = vm) with minimum cost
c(vi), such that d(vi−1,vi) u(i).
Minimum Spanning Trees
2.1 Exercise
(10 points)
Let G = (V, E) be a connected, undirected graph with edge-weight func- tionw:E→R. Letu2Vbeanarbitraryvertex,andlet(u,v)2Ebe the least-weight edge incident on u; that is,
w(u,v) = min{w(u,v0) : (u,v0) 2 E}.
True or false: (u, v) belongs to some minimum spanning tree of G.
2.2 Exercise
(20 points)
Consider the problem of nding the minimum spanning tree connecting n distinct points in the plane, where the distance between two points is the ordinary Euclidean distance. In this problem we assume the distances between all pairs of points are distinct. For each of the following procedures, either argue that it constructs the minimum spanning tree of the n points or give a counterexample.
a) Sort the points in order of their x-coordinate. (You may assume without loss of generality that all points have distinct x-coordinates; this can be achieved if necessary by rotating the axes slightly.) Let (p1, p2, . . . , pn) be the sorted sequence of points. For each point pi, 2 i n, connect pi with its closest neighbor among p1, . . . , pi−1.
b) Draw an arbitrary straight line that separates the set of points into two parts of equal or nearly equal size (i.e. within one). (Assume that this line is chosen so it doesn’t intersect any of the points.) Re- cursively nd the minimum spanning tree of each part, then connect them with the minimum-length line segment connecting some point in one part with some point in the other (i.e. connect the two parts in the cheapest possible manner).
2.3 Exercise
(10 points)
Let G = (V, E) be a weighted graph and let M be a minimum spanning tree of G.
True or False: The path in M between any pair of vertices v1 and v2 must be a shortest path in G.
Chapter 3 Bipartite Graphs
3.1 Exercise
(20 points)
a) (5 points): Show that if every component of a graph is bipartite, then the graph is bipartite.
b) (10 points): Prove that a nite graph is bipartite if and only if it contains no cycles of odd length.
c) (5 points): Show that any tree with at least two vertices is bipartite.
3.2 Exercise
(20 points)
A bipartite graph G = (V, E), where V = L [ R, is d-regular if every
vertex v 2 V has degree exactly d.
a) Prove that for every d-regular bipartite graph, |L| = |R|.
b) Model the maximum d-regular bipartite matching as a max-ow prob- lem. Show that the max-ow value from s to t in the formulation is |L|.
c) Prove that every d-regular bipartite graph has a matching of cardi- nality |L|.
3.3 Exercise
(10 points)
It can be shown that if a bipartite graph on n vertices is d-regular, then the two bipartitions must have n/2 vertices each.
A matching is a set of edges that do not share vertices. On this graph, a perfect matching is one that involves all vertices, or equivalently, has n/2 edges. In this problem we will show that a d-regular bipartite graph can be decomposed into d perfect matchings.
a) (6 points): Prove using either the maxflow-mincut theorem, Hall’s theorem, or some other method of your choice, that a d-regular bi- partite graph will always have a perfect matching.
b) (4 points): Devise an algorithm that decomposes a d-regular bipartite
graph into d perfect matchings in O n200 time. The algorithm in
our solution runs in O n5 time.
Note: this is the easier part of the problem. You may assume part a) in your solution as well
Answer to all problems
Exercises 1.1, page 1
a) First Topological Sort and then dynamic programming (using Dag- Shortest-Paths from Introduction to Algorithms) | O(V + E).
b) Dijkstra’ Algorithm with Fibonacci Heaps | O(E lg V). c) Bellman-Ford’s Algorithm | O(VE).
Exercises 1.2, page 1
Answer: To nd the most reliable path between s and t, run Dijkstra’s algorithm with edge weights w(u, v) = − log r(u, v) to nd shortest paths from s in O(E + V log V ) time. The most reliable path is the shortest path from s to t, and that path’s reliability is the product of the reliabilities of its edges.
Here’s why this method works. Because the probabilities are indepen-
dent, the probability that a path will not fail is the product of the prob-
abilities that its edges will not fail. We want to nd a path from s to t
such that (u,v)2p r(u, v) is maximized. This is equivalent to maximizing
log minimizing
r(u, v) = log r(u, v), which is in turn equivalent to
(u,v)2p − log r(u, v). (Note: r(u, v) can be 0, and log 0 is unde-
ned. So in this algorithm, dene log 0 = −∞. ) Thus if we assign weights w(u, v) = − log r(u, v), we have a shortest-path problem.
Since log 1 = 0, log x < 0 for 0 < x < 1, and we have dened log 0 = −∞, all the weights w are nonnegative, and we can use Dijkstra's algorithm to nd the shortest paths from s in O(E + V log V ) time. Exercises 1.3, page 2 Solution: First, compute the all-pairs shortest path distances δ(i, j) among every pair of cities i and j. Store the values in a table. Then construct a directed acyclic graph H with n(m + 1) nodes. The nodes are labeled as vip, for i 2 {1,2,...,n} and p 2 {0,1,...,m}. Each node vip corresponds to the option of staying at city i on day p. For any i,j 2 {1,2,...,n} where i 6= j and p 2 {1,...,m}, add the edge vi(p−1), vjp in the graph H if δ(i, j) u(p). This means that the customer can bike from city i to city j without exceeding the daily limit. Also, for each node vip, assign a node costci to the node. The lowest cost tour is simply the path from vs0 to vtm where the total node cost is minimum. If vtm is not reachable from vs0, no tour satisfying the requirements exists. We can transform the minimum node cost path problem into a shortest path problem easily. Since the graph is directed, for every edge (u, v) we can assign the cost of node v as its edge weight. This reduces the problem to a shortest path problem, which can be computed using the shortest path algorithm on DAGs (see Section 24.2 in Introduction to Algorithms, Third Edition). Correctness: A path on the graph from v to v corresponds to a s0tm bicycle tour for the m days. Specically, each edge vi(p−1),vjp along the path species a day trip from city i to city j on day p. Note that the edge is present in H if and only if the corresponding day trip does not violate daily mileage constraint. Also, since there is no edge between vi(p−1),vip for any i,p in the graph H, the customer will not stay at the same city on consecutive nights. The transformation of the minimum node-cost path problem into the shortest path problem preserves the cost of corresponding paths (with an oest of the cost of the source node). Therefore the shortest path algorithm on the transformed graph will compute the tour with the lowest cost. Running Time: The all-pairs shortest paths distances can be computed in O n3 time using the Floyd-Warshall algorithm. The graph H contains O(nm) nodes and O n2m edges, so it takes O n2m time to construct the graph. Since H is a DAG, the shortest path on H can be computed in O n2m time. Therefore the overall running time is O n3 + n2m = =O n2(n+m) . Exercises 2.1, page 3 Answer: True. Consider any MST. Assume it doesn't contain (u,v), or else we're done. Since it is a spanning tree, there must be a path from u to v. Let (u,x) be the rst edge on this path. Delete (u,x) from the tree and add (u, v). Since (u, v) is a least weight-edge from u, we did not increase the cost, so as long as we still have a spanning tree, we still have a minimum spanning tree. Do we still have a spanning tree? We broke the tree in two by deleting an edge. So did we reconnect it, or add an edge in a useless place? Well, there is only one path between a given two nodes in a tree, so u and v were separated when we deleted e. Thus our added edge does in fact give us back a spanning tree. Exercises 2.2, page 3 a) This procedure does not work. Notice that in the gure below we must use the line segment (p1, p2) . However, using the segment (p1, p3) would yield a smaller spanning tree. Therefore, this procedure does not produce a MST. b) Solution: This procedure does not work. Notice that in the gure above if we follow the method suggested with the choice of line as in gure, then (p1,p2),(p3,p4),(p1,p4) or (p1,p2),(p3,p4),(p2,p3) would be the tree output by the algorithm. Clearly the tree (p1, p4) , (p1, p2) , (p2, p3) is a MST. Exercises 2.3, page 4 Answer: False. Consider the graph in which V = {a, b, c} and the edges are (a, b), (b, c), (c, a). The weight of the edges are 3,3 and 4 respectively. The MST is clearly (a,b),(b,c). However, the shortest path between a and c is of cost 4 not 6 as seen from the MST. Exercises 3.1, page 5 a) If the components are divided into sets A1 and B1,A2 and B2, et cetera, then let A = [iAi and B = [iBi. b) To show that a graph is bipartite, we need to show that we can divide its vertices into two subsets A and B such that every edge in the graph connects a vertex in set A to a vertex in set B Proceed as follows: Choose any vertex from the graph and put it in set A. Follow every edge from that vertex and put all vertices at the other end in set B. Erase all the vertices you used. Now for every vertex in B, follow all edges from each and put the vertices on the other end in A, erasing all the vertices you used. Alternate back and forth in this manner until you cannot proceed. This process cannot encounter a vertex that is already in one set that needs to be moved to the other, since if it did, that would represent an odd number of steps from it to itself, so there would be a cycle of odd length. If the graph is not connected, there may still be vertices that have not been assigned. Repeat the process in the previous paragraph until all vertices are assigned either to set A or to set B c) This is a trivial consequence of problem b). A tree has no cycles, so it certainly does not contain any cycles of odd length. Exercises 3.2, page 6 a) Every edge in the graph connect a node in L and a node in R. There- fore total number of edges can be expressed as both |L|d and |R|d, which implies |L| = |R|. b) Reduce the bipartite matching problem to a network ow problem, as in gure 26.3 in Introduction to Algorithms: Every edge has unit capacity. Consider the following ow function: every edge out of s or into t has unit ow, and all the other edges have ow 1/d. This is a valid ow, and is maximum since every edge from s is saturated. Therefore, the max-ow value is |L|. c) Since every edge in the max-ow formulation has integral capacity, the Integrality theorem guarantees that there is an integral ow with value |L|. Such integral ow corresponds to a matching of cardinality |L|. Integrality theorem (Th. 26.10). If the capacity function c takes on only integral values, then the maximum ow f produced by the Ford-Fulkerson method has the property that |f| is an integer. More- over, for all vertices u and v, the value of f(u, v) is an integer. Exercises 3.3, page 6 a) The proof is by contradiction. Suppose not, then by Hall's theorem there exists a set S A that's adjacent to fewer than |S| vertices. The number of edges leaving S is d|S|. For these edges to be distributed to fewer than |S| neighbors, some vertex must have degree at least d + 1. A contradiction with the assumption that the graph is d -regular. b) Consider an algorithm that: (i) nd a perfect matching; (ii) remove it, repeat on the resulting graph. Since the perfect matching has degree 1 at each vertex, removing it results in a graph with degrees d − 1 at the vertices. So by part a) we always can nd such a matching. As d n, and perfect match- ingstakeuptoO n2m =O n5 tond,theruntimeofthisis O nn4 ,whichisO n5 . 程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com