edited by
17,420 views
60 votes
60 votes

Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_{k+1}) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in which no vertex appears more than once.

Let $A$ be an $n \times n$ array initialized as follows:

$$A[j,k] = \begin{cases} 1 \text {,   if } (j,k) \in E \\ 0 \text{,   otherwise} \end{cases}$$

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 termination of the above algorithm?

  1. $A[j,k] \leq n$
  2. If $A[j,j] \geq n-1$ then $G$ has a Hamiltonian cycle
  3. If there exists a path from $j$ to $k$, $A[j,k]$ contains  the longest path length from $j$ to $k$
  4. If there exists a path from $j$ to $k$, every simple path from $j$ to $k$ contains at most $A[j,k]$ edges
edited by

4 Answers

Best answer
68 votes
68 votes

D is correct.

Consider a graph with $2$ nodes and one edge from $V_1$ to $V_2$,

Running the above algorithm will result in $A$ being 

$$\begin{array}{|l|l|l|} \hline \textbf{A} & \textbf{1} & \textbf{2} \\\hline \textbf{1} & \text{1} & \text{2} \\\hline \textbf{2} & \text{1} & \text{2} \\\hline \end{array}$$

Clearly options B and C are wrong. Since

  1. $A[1][1]$ and $A[2][2] > n-1$ and there exists no Hamiltonian cycle. Hence invalid.
  2. The longest path between $V_1$ and $V_2$ is $1$, but $A[1][2]$ is $2$, which is invalid. And no path between  $V_2$ and $V_1$ yet $A[2][1] = 1$ // it should be max cost path between j and k, not path length.

Hence A or D could be valid.

Now consider a graph with $2$ nodes and two edges, one from  $V_1$ and $V_2$ and other form $V_2$ and $V_1$. Running the above algorithm will result in $A$ being
$$\begin{array}{|l|l|l|} \hline \textbf{A} & \textbf{1} & \textbf{2} \\\hline \textbf{1} & \text{2} & \text{3} \\\hline \textbf{2} & \text{3} & \text{4} \\\hline \end{array}$$

Hence option $A$ is invalid, as $A[i][j]$ can be $>n.$

D is correct

edited by
23 votes
23 votes

G=(V,E) has n vertices.

(Vi,Vj) can have a path more than 1 edges

if that is the case we will take maximum length path

A[j,k] = max(A[j,k], A[j,i] + A[i,k]);

Now take an example with 2 vertices

  1 2
1 0 1
2 0 0

Here we can check option B) A[1,1]=0<(n-1)=2-1=1

So, this option false

Now, take another graph where loop is present

In option C)says A[j,k] contains  the longest path length from to k

But if there is a loop present then longest path will contain the loop.

See here A[1,1]=1->2->1

But according to algorithm we can work with only simple path

So, this option also false.

Now, A) option

See, A[1,2] max length of path is 3, as 1 contain a self loop.

A[1,2]=3>2=n [where n is number of vertices

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

it is completely TRUE. As it is clearly mention simple path.

So, Ans D)

10 votes
10 votes

 

An example to support answer D.

 

3 votes
3 votes
Solution:D

Tracing this algorithm on a simple graph with two nodes(with only one edge form node 1 to node 2) revels that the only statement that can be true about this algorith is D.
Answer:

Related questions

24 votes
24 votes
5 answers
2
Kathleen asked Sep 16, 2014
12,875 views
Consider the following graph: Among the following sequences:abeghfabfehgabfhgeafghbeWhich are the depth-first traversals of the above graph?I, II and IV onlyI and IV only...