PUERTA | PUERTA-CS-2003 | Pregunta 70

Sea G (V, E) un grafo dirigido con n vértices. Un camino de vi _a v _j en G es una secuencia de vértices (v _i , v _i+1 , ……., v _j ) tal que (vk, v _k+1 ) ∈ E para todo k en i a j – 1. Un camino simple es un camino en el que ningún vértice aparece más de una vez. Sea A una array nxn inicializada de la siguiente manera

Considere el siguiente algoritmo.

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]); 

¿Cuál de las siguientes afirmaciones es necesariamente cierta para todos los j y k después de la terminal del algoritmo anterior?
(A) A[j, k] ≤ n
(B) Si A[j, k] ≥ n – 1, entonces G tiene un ciclo hamiltoniano
(C) Si existe un camino de j a k, A[j, k ] contiene la lente de ruta más larga de j a k
(D) Si existe una ruta de j a k, cada ruta simple de j a k contiene la mayoría de los bordes A [j, k]

Respuesta: (D)
Explicación:

In the original input matrix,  A[j , k] is 1 if there
is an edge from j to k, else 0.

Below expression is important to note:

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

This expression puts the count of maximum edges on a path from
j to k.  In this expression, we consider every vertex k that can 
become an intermediate vertex and can give longer path.

Cuestionario de esta pregunta