UPDATE: in the original version of the algorithm, the matrix A was being updated
ID: 3812940 • Letter: U
Question
UPDATE: in the original version of the algorithm, the matrix A was being updated too early in the Main Loop. We've updated the algorithm so that now a new matrix A1 stores all the updates, and then the updates are transferred over to A 1 def connected (A): n len (A) This is the number o vertices in the graph. 4 First, set diagonal to 1, since every vertez is connected to itself. 5 for i in range (n) A[i] [i] 8 for q in range (1, ceil (log(n)) 1 Main Loop g 1,2 ceil(log In) g A1 new n by n array containing all zeros UPDATE: Assume this takes n n steps 10 Find new connectedness information for i in range (n) for j in range (n) for k in range (n) 13 if Ali] [k] 1 and ACk] [j] 14 A1 [i] [j] UPDATE: A1 stores new connectivity information. 16 17 for i in range (n) UPDATE: Change A to store the new connections. 18 for j in range (n) 19 if A[i] [j] If ALijlij is already 1, don't need to typ date. A [i] [j] A1 [i] [j] 23 Check if the graph is connected at this point. all-conn True 24 for i in range (n) 25 ALO] [i] if 26 all-conn False 27 break 28 29 if all conn return True 33 The loop has ended and *not returned early. 34 return FalseExplanation / 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.
1. Here we want to prove that for every vertex in adjacency matrix, if the respective value in matrix is 1, i.e. for all vertex I,j if A[i][j] = 1 , than there is path between i and j with length at most 2q . proof of concept for this for the algorithm given is as follows: -
Property to prove: i, j V, A[i][j] = 1 PathLength(G, i, j, 2q )
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).
Base Case: Base case is q = 1. i.e. for first iteration, the property holds for q = 1 as if there is value 1 in adjacency matrix for I,j it means there is a direct path between I,j and as for first iteration , no intermediate vertex distance is updated, So there is a path between i and j , thus property is proved for base case. i.e. if A[i][k] = 1 and A[k][j] = 1 then A[i][j] = 1 where k is the first immediate neighbor of i. Now q= 1 there for adding paths of A[i][k] and A[k][j] we get 2 i.e path length is 2.
Inductive Step: Here we assume that the property holds at q = k, i.e. after kth iteration, the algorithm has updated the adjacency matrix and have values as A[i][ki] = 1 and A[ki][j] = 1, where ki tends from first to kth immediate neighbor.
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.
As all the values in array is 1, therefore there is a path and the length of path is addition of all which comes out to be 2^k+1. So by induction it is proved.
2. 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: -
Property to prove: i, j V, A[i][j] = 0 ¬ PathLength(G, i, j, 2q )
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).
Base Case: Base case is q = 1. i.e. for first iteration, the property holds for q = 1 as if there is value 0 in adjacency matrix for I,j it means there is no direct path between I,j and as for first iteration , no intermediate vertex distance is updated, So there is no path between i and j , thus property is proved for base case. i.e. if A[i][k] = 0 and A[k][j] = 0 then A[i][j] = 0 where k is the first immediate neighbor of i.
Inductive Step: Here we assume that the property holds at q = k, i.e. after kth iteration, the algorithm has updated the adjacency matrix and have values as A[i][ki] = 0 and A[ki][j] = 0, where ki tends from first to kth immediate neighbor.
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.
3. Now using first two parts, if connected returns true, that means all values in array are updated to 1 so there are paths from each vertex to each vertex, So the graph is connected. This is proved by 1st proof.
On the other hand, if connected returns false, then it means at least 1 or all values in array are 0, so graph is not connected as there is no path. This is proved by 2nd proof.
Related Questions
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.