UGC NET CS 2014 DecPaper2
October 7, 2023Environment
October 7, 2023Graphs
Question 4

Let G = (V,E) be a directed graph with n vertices. A path from v_{i} to v_{j} in G is sequence of vertices (v_{i}, v_{i+1}, ……., v_{j}) such that (v_{k}, v_{k+1}) ∈ E for all k in i through j1. A simple path is a path in which no vertex appears more than once. Let A be an nxn array initialized as follow.
Consider the following algorithm.
for i = 1 to n for j = 1 to n for k = 1 to n A [j,k] = max (A[j,k] (A[j,i] + A [i,k]);
Which of the following statements is necessarily true for all j and k after terminal of the above algorithm?
A[j,k] ≤ n


If A[j,j] ≥ n1, then G has a Hamiltonian cycle


If there exists a path from j to k, A[j,k] contains the longest path length from j to k


If there exists a path from j to k, every simple path from j to k contains at most A[j,k] edges

Question 4 Explanation:
Here, we have two functionalities i.e., from j to k, there exists a path then it results otherwise 0.
If there exist a path then it results
A[j,k] = max(A[j,k], A[j,i]+A[i,k])
i.e., if there exists a path from j to k, every simple path from j to k contains the atmost A[j,k] edges.
Correct Answer: D
Question 4 Explanation:
Here, we have two functionalities i.e., from j to k, there exists a path then it results otherwise 0.
If there exist a path then it results
A[j,k] = max(A[j,k], A[j,i]+A[i,k])
i.e., if there exists a path from j to k, every simple path from j to k contains the atmost A[j,k] edges.
Subscribe
Login
0 Comments