211L9Solutions

Lecture 9

1. Prove that if G = (V,E) is a tree then there exists exactly one path from any vertex x in G to any other vertex y in G.

By definition a tree is connected and contains no cycles.

To prove by contradiction, Say there are two or more paths from a given vertex x to y. If you look at these two paths in isolation, there is a clear cycle. For an n number of paths between two nodes, there are n! loops. This contradicts the property of a tree and therefore there can only be one path between the vertices x and y in G.

2. Prove that the following statements for a connected graph G = (V,E) are equivalent:

• (a) The graph G is a tree.
• (b) If an edge is removed from E then the resulting graph is not connected.
• (c) If a new edge is put into E then the resulting graph contains a cycle.

If the graph is a tree, then there is only one path from two vertices in the graph x to y. If an edge between these two is removed, then there is no path between them and they are no longer connected. In other words (a) and (b) are equivalent.

If the graph is a tree, then there is only one path from two vertices in the graph x to y. If an edge is added to this graph, then there can potentially be two paths from x to y. If it is the case that by adding an edge to the graph and the resulting graph contains a cycle, then it must be the case that the current graph is a tree.

3. This exercise extends the SpanningT ree2(G) algorithm. A connected graph G = (V,E) is weighted if every edge e in the graph has exactly one number w(e) associated with it, called the weight of e. Let T = (V,E) be a spanning tree of G. The weight of T , denoted by w(T ), is the sum of all weights of the edges of T . We say T = (V1,E1) is a minimal spanning tree for G if the following conditions are satisfied:

• (a) T is a spanning tree of G.
• (b) The weight of any other spanning tree for G is not smaller that the weight of T .

Modify the algorithm SpanningTree2(G) to build a minimal spanning tree for a given weighted connected graph G. Prove the correctness of your algorithm.

4. Consider the bipartite graph in Figure1. On this graph consider the reachability games for the following values of X: {a, b}, {7}, {e, 3, 5}, {a, 1}, and {0, a, b}. For each of these reachability games find the winning vertices for Player 0 by computing their ranks.

x:{a, b} X0 = {a,b}, X1 = {2,6,4}, X2 = {e,f,d}, X3 = {5,3}, X4 = {j,i}, X5 = {7}, X6 = 0.

x:{7} X0 = {7}, X1 = 0.

x:{e, 3, 5} X0 = {e,3,5}, X1 = {b,j}, X2 = {6,i,m}, X3 = {f}, X4 = {7}, X5 = {7}, X6 = 0.

x:{0, a, b} X0 = {0,a,b}, X1 = {2,6,4}, X2 = {e,f,d,3,1}, X3 = {5,m}, X4 = {j,i,k,c}, X5 = {7}, X6 = 0.

5. Let 􀀀 be a reachability game on a bipartite graph G = (V0 ∪ V1,E) with set X ⊆ V . Let v0, . . . , vk be a play. We say that this play is produced by k moves made by the players. Prove that rank(v) = n if and only if Player 0 can reach set X in at most n moves made by the players no matter what moves the opponent makes.

Base case. Assume that rank(v) = 0. Then, by the definition of X0, v ∈ X0. Since X0 = X, any play from v is won by Player 0.

• Our inductive assumption is this:

All the vertices q such that rank(q) ≤ k are winning for Player 0.

Now, let the rank of v be k + 1. For the vertex v there are two cases. Using the inductive hypothesis we want to show that v is a winning vertex for Player 0.

• Case 1: v ∈ V1. In this case, for every edge (v, u) it must be the case that rank(u) ≤ k. Thus, all moves of Player 1 from v go to vertices of strictly smaller ranks. All the vertices of smaller ranks are, by inductive hypothesis, winning for Player 0. Therefore, no matter where Player 1 moves from v, the move goes to a vertex that is a winning vertex for Player 0. Therefore v is a winning vertex for Player 0.
• Case 2: v ∈ V0. In this case there must exist an edge (v, u) such that rank(u) = k since rank(v) = k +1. Thus, Player 0 does the following. From vertex v, the player moves to u. Since rank(u) = k, we can apply the inductive hypothesis by which Player 0 can guarantee a win from u. Therefore v is a winning vertex for Player 0. Thus, we have proved that every ranked vertex is a winning vertex for Player 0.

6. Write down an algorithm that takes as input a reachability game and outputs the winning vertices for Player 0 and winning vertices for Player 1.

7. Let G be a reachability game. Fix a positive integer n. We say that a vertex v is n-winning if Player 0 can guarantee that the set X is reached at least n times no matter what the opponent does. Design an algorithm that finds all n-winning vertices. Prove correctness of your algorithm.

• Basis.

Set X0 = X. For all v ∈ X0, declare rank(v) = 0.

• Inductive Step.

Our induction hypotheses assumes that we have the following: 1. We have built sets X0, X1, . . ., Xn. 2. For every vertex v, if v ∈ Xi then rank(v) = i. In case v does not belong to any of the sets X0, X1, . . ., Xn, the rank(v) has not yet been defined.