HW4_latest

CSC 505, Homework 4 1. Purpose: Learn about Euler tours (12 points) . Please solve Problem 20-3 of our textbook. a. Show that G has a Euler tour if and only if in-degree(v)=out-degree(v) for each vertex v. First, we'll show that it is necessary to have in degree equal out degree for each vertex. Suppose that there was some vertex v for which the two were not equal, suppose that in-degree( v )−out-degree( v ). Note that we may assume that in degree is greater because otherwise we would just look at the transpose graph in which we traverse the cycle backwards. If v is the start of the cycle as it is listed, just shift the starting and ending vertex to any other one on the cycle. Then, in whatever cycle we take going though v , we must pass through v some number of times, in particular, after we pass through it a times, the number of unused edges coming out of v is zero, however, there are still unused edges going in that we need to use. This means that there is no hope of using those while still being a tour, because we would never be able to escape v and get back to the vertex where the tour started. Now, we show that it is sufficient to have the in degree and out degree equal for every vertex. To do this, we will generalize the problem slightly so that it is more amenable to an inductive approach. That is, we will show that for every graph G that has two vertices v and u so that all the vertices have the same in and out degree except that the indegree is one greater for u and the out degree is one greater for v , then there is a Euler path from v to u . This clearly lines up with the original statement if we pick u = v to be any vertex in the graph. We now perform induction on the number of edges. If there is only a single edge, then taking just that edge is a Euler tour. Then, suppose that we start at v and take any edge coming out of it. Consider the graph that is obtained from removing that edge, it inductively contains a Euler tour that we can just post-pend to the edge that we took to get out of v . b. Describe an O ( E )-time algorithm to find a Euler tour of G if one exists. (Hint: Merge edge-disjoint cycles.) To get the Euler circuit, we can just arbitrarily walk any way that we want so long as we don't repeat an edge, we will necessarily end up with a valid Euler tour. Algorithm EULER-TOUR(G) color all edges WHITE let (v, u) be any edge let L be a list containing v while there is some WHITE edge (v, w) coming out of v color (v, w) BLACK v = w append v to L

Example : For example, we have vertices A, B, C, D, E and edges AB, BA, AC, CA, CD, DC, DE, ED To find an Euler tour using the EULER-TOUR algorithm for the given graph with vertices A, B, C, D, E, and edges AB, BA, AC, CA, CD, DC, DE, and ED, let's go step by step: 1. Initialize all edges to WHITE:  AB: WHITE  BA: WHITE  AC: WHITE  CA: WHITE  CD: WHITE  DC: WHITE  DE: WHITE  ED: WHITE 2. Start with an arbitrary edge. Let's choose edge AB, and let L be a list containing vertex A:  L: [A]  Current vertex (v): A 3. Check for other WHITE edges coming out of vertex A:  Out of A, we have two WHITE edges, AB and AC.  We will choose the edge AB, update its color to BLACK, and move to vertex B. 4. Append B to the list L:  L: [A, B]  Current vertex (v): B 5. Check for other WHITE edges coming out of vertex B: Out of B, we have one WHITE edge, BA (which is the reverse of AB, so we won't choose it). But there are no other WHITE edges. 6. Since there are no more WHITE edges coming out of vertex B, we backtrack to the previous vertex A, where we have one more WHITE edge to explore. 7. Move to vertex C using the edge AC and update its color to BLACK:  L: [A, B, C]  Current vertex (v): C 8. Check for other WHITE edges coming out of vertex C: Out of C, we have one WHITE edge, CA (which is the reverse of AC, so we won't choose it). But there are no other WHITE edges. 9. Since there are no more WHITE edges coming out of vertex C, we backtrack to the previous vertex B. 10. Move to vertex D using the edge CD and update its color to BLACK:

Let's prove these properties: Property 1: The algorithm covers all edges.  Initially, all edges in the graph are colored as WHITE, indicating that none of them have been traversed.  The algorithm explores edges while they are WHITE, marking them as BLACK after traversal.  In each step of the algorithm, it chooses a WHITE edge (v, w) coming out of vertex v.  When there are no more WHITE edges coming out of a vertex, the algorithm backtracks to a previous vertex, effectively ensuring that all edges are eventually explored. Therefore, the algorithm ensures that it covers all edges in the graph. Property 2: The algorithm returns a closed tour.  The algorithm starts by choosing an arbitrary edge (v, u) and adds vertex v to the list L.  The algorithm continuously adds vertices to list L as it explores edges.  Since the algorithm starts and ends with the same vertex (the initial vertex, v), it naturally results in a closed tour. Property 3: The algorithm maintains edge-disjoint cycles.  When the algorithm explores an edge (v, w) by marking it as BLACK, it follows a path until it reaches a vertex (w) with no more WHITE edges to explore.  At this point, the algorithm backtracks to the previous vertex (v) and looks for other WHITE edges coming out of it. This process continues until there are no more WHITE edges coming out of any vertex.  During this exploration, the algorithm may encounter edge-disjoint cycles. These cycles are essentially explored separately and merged together as the algorithm progresses, ultimately forming a single Euler tour that covers all edges in the graph. Given these three properties, we can conclude that the EULER-TOUR(G) algorithm correctly finds a Euler tour in a graph if one exists. It ensures that all edges are traversed exactly once, the resulting tour is closed, and it maintains edge-disjoint cycles, which are merged to form a valid Euler tour. Time complexity: The algorithm takes running time O ( ∣ E ∣ ) because the for-loop will run for every edge and takes a constant amount of time. Also, the process of initializing each edge's color will take time proportional to the number of edges. 2. Purpose: Reinforce your understanding of MST algorithms, and practice algorithm design (14 points). Let T be the Minimum Spanning Tree of a graph G=(V, E, w).

Suppose g is connected, |E|≥|V|, and all edge-weights are distinct. Denote T* the MST of G and ST(G) be the set of all spanning trees of G. A second-best MST is a spanning tree T such that w(T) =min{w(T): T ϵ ST(G)-{T*}}. a. (4 points) Show that T* is unique but that the second-best MST T2 need not be unique. T* is unique: Suppose there are two minimum trees, A and B. Let ‘e’ be the edge with the smallest cost that occurs in just one of A, and B. Suppose it is in A but not B. Suppose e is the edge PQ. Then B must contain a path from P to Q which is not simply the edge e. If we add e to B, then we get a cycle. If all the other edges in the cycle were in A, then A would contain a cycle, which it cannot. Ergo the cycle must contain an edge f, not in A. Since f is in B but not A, and all edge costs are different, the cost of f must be greater than the cost of e. If we replace f by e we get a spanning tree with a smaller total cost. Contradiction. T2 is not unique: To see that the second best minimum spanning tree need not be unique, we consider the following example graph on four vertices. Suppose the vertices are (a, b, c, d), and the edge weights are as follows: a b c d a - 1 4 3 b 1 - 5 2 c 4 5 - 6 d 3 2 6 - Then, the minimum spanning tree has weight 7, but there are two spanning trees of the second-best weight, 8. b. (4 points) Prove that G contains an edge (u,v) ϵ T* and another edge (s,t) ∉ T* such that (T*-{(u,v)}) ∪ {(s,t)} is a second-best minimum spanning tree of G. We are trying to show that there is a single edge swap that can demote our minimum spanning tree to a second best minimum spanning tree. In obtaining the second best minimum spanning tree, there must be some cut of a single vertex away from the rest for which the edge that is added is not light, otherwise, we would find the minimum spanning tree, not the second best minimum spanning tree. Call the edge that is selected for that cut for the second best minimum spanning tree (x, y). Now, consider the same cut, except look at the edge that was selected when obtaining T, call it (u, v). Then, we have that if consider T-{(u, v)} {(x, y)), it will be a second best minimum spanning tree. This is because if the second best minimum spanning tree also selected a non-light edge for another cut, it would end up more expensive than all the minimum spanning trees. This means that we need for every cut other than the one that the selected edge was light. This means that the choices all align with what the minimum spanning tree was. c. (6 points) Please use Kruskal’s algorithm to design an efficient algorithm to

(B, C), (C, D), (D, A), weight = 2 + 3 + 4 = 9 3. Iteration 2: Exclude (B, C), possible second-best MST: (A, B), (C, D), (D, A), weight = 1 + 3 + 4 = 8 4. Iteration 3: Exclude (C, D), possible second-best MST: (A, B), (B, C), (D, A), weight = 1 + 2 + 4 = 7 5. MST with lowest weight is generated in iteration 3: Second-best -> (A, B), (B, C), (D, A), weight = 1 + 2 + 4=7 Proof of the correctness: In Problem b) we have learned that G contains an edge (u,v) ϵ T* and another edge (s,t) ∉ T* such that (T*-{(u,v)}) ∪ {(s,t)} is a second-best minimum spanning tree of G. In the iteration where we exclude (u,v), Kruskal has all edges of a second-best MST available. Since the algorithm cannot find a better MST (T* is unique, as shown in Problem a), Kruskal will report a second-best MST in this iteration. Time complexity: So, the overall time complexity will be O(ElogV+E+VE) = O(VE). If you sort every time the complexity is O(VElogV), this slower approach is also ok since we haven’t asked for the best possible implementation. 3. Purpose: Reinforce your understanding of Dijkstra’s shortest path algorithm, and practice algorithm design (16 points). Suppose you have a weighted, undirected graph G with positive edge weights and a start vertex s . a. (6 points) Describe a modification of Dijkstra’s algorithm that runs (asymptotically) as fast as the original algorithm, and assigns a binary value usp[ u ] to every vertex u in G , so that usp[ u ]=1 if and only if there is a unique shortest path from s to u . In addition to your modification, be sure to provide arguments for both the correctness and time-bound of your algorithm and an example. Textual description: The problem asks us to modify Dijkstra’s algorithm to determine if there is a unique shortest path from source vertex s to vertex u. In our solution, the basic Dijkstra algorithm will work as before, but we will make a few changes to the RELAX function of Dijkstra’s algorithm. We consider an array usp[] which will tell us whether a unique shortest path ending in a particular vertex exists. By default, all array values will be set NIL,

usp[s] will be set 1. The basic idea is that if there exists a second shortest path from a vertex u to v, then either usp[p[v]]=false, or two different shortest paths of equal value converge at v, i.e., u≠p[v] and d[v]=d[u]+w[u,v]. Thus, whenever we encounter d[v]>d[u]+w[u,v] we assign u the usp-value of its predecessor, i.e., usp[v]=usp[u], or, in case of d[v]=d[u]+w[u,v] and u≠p[v] we set usp[v]=0, indicating that the shortest path to vertex v is not unique. In the end, the vertices for which there exists a unique shortest path will have an entry 1 in the array usp[]. For vertices where the shortest path is not unique, the entry will be 0, and vertices that cannot be reached from s will have NIL. Pseudo Code: DIJKSTRA(G, w) INITIALIZE(G,s) // s is the source vertex S = {} Q = G.V while not EMPTY(Q) u = EXTRACT-MIN(Q) S = S {u} ∪ for each vertex v G.Adj[u] do ϵ if v S ∉ RELAX (u,v,w) RELAX(u,v,w) if d[v] = d[u] + w(u,v) and u≠p[v] usp[v] = 0 if d[v] > d[u] + w(u,v) d[v] = d[u] + w(u,v) p[v] = u usp[v] =usp[u] INITIALIZE(G,s) For every vertex v in G.V d[v] = ∞ p[v] = NIL usp[v] = NIL d[s] = 0 usp[s] = 1 // initialize usp[s] as 1, since path to source is always unique Example :

The final set is given as: S = {4, 1, 2, 3, 5} usp = [1, 1, 1, 1, 0] For vertices 1,2 and 3, usp value is 1. Hence, there is a unique path from the source vertex 4 to these vertices. But for vertex 5, usp value is 0. This means that there are multiple paths from source vertex 4 to vertex 5(4-1-5 and 4-2-5) Proof of correctness: The above algorithm uses the assumption that we have positive edge weights. Since our algorithm follows Dijkstra’s algorithm to compute shortest-path estimates d and predecessors, these values are computed correctly. To see that the usp-values are computed correctly we use an induction argument. Our induction assumption is that at the time a vertex v enters S usp[v], as well as the usp-values of all previously entered vertices, are correct. A correct induction-start is guaranteed by our initialization usp[s]=1. Now assume that our induction assumption is true, and v enters S. Consider v’s predecessor pv=p[v]. If there is only one shortest path from s to v, then usp[pv]=1, and v inherited this usp-value then pv was relaxed. If there are multiple shortest paths from s to v, but all paths traverse pv, then usp[pv]=0, and again, v inherited this usp-value then pv was relaxed. In case there are multiple shortest paths from s to v, and we have multiple different predecessors pv 1 , pv 2 , …, pv k of v, then we get d[v]=d[pv i ]+w(pv i ,v) for i=2,…,k, and usp[v] was assigned 0 then pv 2 ,…,pv k were relaxed. In either case, usp[v] stores the correct value when v enters S. Time Complexity: Our modifications to the original algorithm are: 1. During initialization, adding and initializing an array usp[] of size |V|. This does not affect the asymptotic cost of the initialization routine. 2. Adding the conditionals “if (d[v] = d[u] + w(u,v) and u≠p[v]) then usp[v] = 0,” and if “d[v] > d[u] + w(u,v) then usp[v] = 0” in the RELAX-function. Since both modifications execute in O(1)-time, this does not affect asymptotic contributions of the RELAX-function. Thus, the time complexity of the modified algorithm remains that of the original Dijkstra algorithm. b. Dijkstra.java file uploaded to moodle