Recall that we say a graph G (V, E) is (fully) connected if and only if for ever
ID: 3809663 • Letter: R
Question
Recall that we say a graph G (V, E) is (fully) connected if and only if for every pair of vertices u, v elementof V, u and v are connected in G. Also recall (from Problem Session 11) that if the vertex set is V - {0, 1, ..., n - 1}, then we can represent a graph in a program as a two-dimensional n-by-n array A, where the entry A[i][j] is set to 1 if vertices i and j are adjacent (the edge), and 0 if they aren't. The following algorithm takes as input such an array, and returns True if the algorithm is connected, and False otherwise. def connected (A): n = len(A) # This is the number of vertices in the graph. # First, set diagonal to 1, since every vertex is connected to itself. for i in range(n): A [i] [j] = 1 for q in ranged, ceil(log(n)) + 1): # Main Loop: q = 1, 2, ..., ceil (log (n)) A1 = new n by n array containing all zeros # UPDATE: Assume this takes n*n steps #Find new connectedness information for i in range(n): for j in range(n): for k in range(n): if A[i] [k] == 1 and A[k] [j] == 1: A1[i][j] = 1 # UPDATE: A1 stores new connectivity # information for i in range(n): # UPDATE: Change A to store the new connections. for j in range(n): if A[i] [j] == 0: # If A[i] [j] is already 1, don't need to update. A[i] [j] = A1[i] [j] Check if the graph is connected at this point. all_conn = True for i in range(n): if A[0] [i] == 0: all_conn = False break if all_conn: return True # The loop has ended and *not* returned early. return False This algorithm starts with an adjacency matrix A arid continually updates the entries of A to represent new connectedness relationships between pairs of vertices. Proving correctness. To formally prove the correctness of this algorithm, we need the following predicate, where G is a graph, u and v are vertices in the graph, and d elementof N. PathLength(G, u, v, d): "there is a path in G between u and v of length at most d" Using this predicate, we can state the key property of graphs that makes the connected algorithm work: Forall G = (V, E), Forall u, v elementof V, Forall d elementof N, PathLength(G, u, v, 2d) doubleheadarrow (exist w elementof V, PathLength(G, u, w, d) A PathLength(G, w, v, d)) (a) Let n elementof Z^+ with n > 1, and consider running connected on an n-by-n adjacency matrix representing a graph G = (V, E), where V = {0, 1, ..., n - 1}. Prove by induction on q that at the end of iteration q of the Main Loop, the following is true: Forall i, j elementof V, A[i][j] = 1 rightarrow PathLength(G, i, j, 2^q) (b) Now in the same context as part (a), prove by induction on q that at the end of the iteration q of the Main Loop, the following is true: Forall i, j elementof V, A[i][j] = 0 rightarrow PathLength(G, i, j, 2^q) (You might recognize that parts (a) and (b) together prove an "if and only if.")Explanation / Answer
Here Algorithm is actually updating the adjacency matrix in a level by level form. i.e. at each iteration path between two vertices is determined by checking if path is there between the immediate neighbors. For eg . After iteration 2, if A[i][k] = 1 and A[k][j] = 1, then A[i][j] = 1, i.e. there is a path between vertex I and j. This property is checked till second immediate neighbor.
Here we want to prove that for every vertex in adjacency matrix, if the respective value in matrix is zero, i.e. for all vertex I,j if A[i][j] = 0 , than there is no path between i and j with length at most 2q . proof of concept for this for the algorithm given is as follows: -
Where V is the vertex and A is the adjacency matrix and PathLength describes that there is a path between I and j with length at most 2q where 1 q |logn| - 1(Assumption 1).
Now we need to prove that property holds for q = k+1. According to our assumption, we have values till kth neighbors. So value of A[i][k+1] and A[k+1][j] needs to be determined.
A[i][k+1] = A[i][ki] && A[ki]A[k+1]
Where ki tends from first to kth neighbor.
Now because property holds for q = k, A[i][ki] = 0, So A[i][k+1] will always be zero as per the property and our assumption.
Therefore, for q = k+1, as A[i][k+1] = 0, therefore, there is no path between I and k+1th neighbor of I, so property holds for q+1 also.
(Because there is && operator in between, if any of the array value is 0, then the resultant value is also 0)
Since the property holds for q = k+1, by the property of inductive hypothesis, the algorithm’s correctness is proved.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.