Algorithms 3027/3927 2019 Semester 1
Task 1:
1. c(x,y) = 1, c(y,z) = 2, c(x,z) = 3. x
13
yz
2
Assignment 1 Example Solution
The University of Sydney School of Computer Science
2. A = {y}.
3. Minimum spanning tree X = {(x, y), (y, z)}.
x
1
yz
2
4. Thevertexy¡ÊAhasdegX(y)=2>1. Task 2
For this problem, note that the statement to be proved is trivially true when |V \ A| = 1. Henceforth, we shall assume |V \ A| > 1.
Lemma 1. (V \A,F \FA) is connected.
Proof. To prove that (V \ A, F \ FA ) is connected, we need to show that every pair of vertices u and v in V \ A is connected by a path consisting of edges in F \ FA. Since (V, F ) is connected, let P be a simple path1 consisting of edges in F that connects u and v. Since P does not repeat any edge and each vertex of A is incident to exactly one edge of F, we get that P does not visit any vertex in A and so P consists of edges entirely in F \ FA. Thus, (V \ A, F \ FA) is connected.
Theorem 2. (V \A,F \FA) is a minimum spanning tree of V \A.
Proof. First,weargueusinganexchangeargumentthat(V\A,F\FA)isaminimumconnectedsubgraph on the vertex set V \ A. Suppose, towards a contradiction, that this is not the case, i.e. there exists a connected subgraph (V \A,X) of lower cost. Then we can replace the set of edges F \FA with X and end up with a solution (V, X ¡È FA) that is still connected, satisfies the degree constraints and has lower cost. This contradicts the optimality of F , so it must be the case that (V \ A, F \ FA) is a minimum connected subgraph on the vertex set V \ A.
Now, observe that (V \ A, F \ FA) is acyclic. This is because, otherwise, there is some edge e in a cycle which we can remove to obtain a connected subgraph of lower cost, contradicting the fact that (V \ A, F \ FA ) is a minimum connected subgraph. Since (V \ A, F \ FA ) is acyclic, we conclude that it is a minimum spanning tree.
1Recall that a simple path repeats no vertices and no edges.
1
Task 3
Description
Assume adjacency list representation.
1. Make a graph G¡ä by deleting A and the edges incident on A from the graph.
2. Run Prim¡¯s algorithm on G¡ä to obtain a MST T of V \ A.
3. Foreachvertexu¡ÊA,findtheminimumcostedge(u,v)suchthatv¡ÊV \A.
4. Let H be the union of the set of edges of the MST, and of the minimal cost edges obtained in step 3.
5. Return H.
Prove correctness
Theorem 3. The set of edges H found by our algorithm is an optimal solution.
Proof. First, for each vertex u ¡Ê A, our algorithm chooses exactly one edge attached to u to be in H so degH(u) = 1. Next, we argue that the subgraph (V,H) is connected. Since H contains a spanning tree T of V \A, there is a path in H between every pair of vertices in V \A. For each vertex u in A, let s(u) be its unique neighbor in H; note that by definition of our algorithm, s(u) is in V \ A. Now, consider a vertex u ¡Ê A. It is connected to every vertex v ¡Ê V \ A by a path consisting of the edge (u, s(u)) and a path from s(u) to v. It is also connected to every vertex v ¡Ê A by a path consisting of a path from u to s(v) and the edge (s(v),v). Therefore, (V,H) is connected and degH(u) = 1 for every u ¡Ê A.
Finally, we argue that the cost of H is optimal. Let F be an optimal solution and FA be the subset of edges incident to A. We have that each vertex in A is attached to exactly one edge of FA. So, for each vertex v in A, the subset FA has exactly one edge between v and some vertex in V \ A, and this edge is one of the cheapest among all edges between v and some vertex in V \ A (otherwise, we can substitute with a cheaper edge and obtain a solution of cheaper cost).
Together with Task 2, we now know that F consists of a minimum spanning tree on V \ A, and then for each v ¡Ê A chooses one of the cheapest edge between v and V \ A. This matches our algorithm¡¯s solution and so it is optimal.
Prove complexity
Theorem 4. Our algorithm runs in time O(m log n), where n is the number of vertices in G and m is the number of edges.
Proof. Assuming adjacency list representation2
1. Creating G¡ä: O(n + m), as we have to iterate over all the vertices and edges.
2. Prim¡¯s algorithm on G¡ä. The graph G¡ä has at most n vertices and at most m edges, so the upper bound for Prim¡¯s is still O(m log n).
3. Finding minimal cost edges. For each of at most n vertices, we must iterate over the edges incident on them. There will be at most 2m edges across all their adjacency lists, so this takes O(m) time.
4. Taking the union of the MST edges and the minimal edges to attach A. As these are distinct sets, we can just iterate over each to combine them into a list, in O(m) time.
5. In total O(n+m)+O(m log n)+O(m)+O(m) = O(n+m log n). For a connected graph, n = O(m), so we may simplify this to O(m log n).
2In this case an adjacency matrix wouldn¡¯t actually be worse, because m ¡Ê ¦¨(n2) in a complete graph. 2