Рубрики

ВОРОТА | GATE-CS-2003 | Вопрос 70

Пусть G (V, E) — ориентированный граф с n вершинами. Путь от v i до v j в G — это последовательность вершин (v i , v i + 1 , ……., V j ) такая, что (vk, v k + 1 ) ∈ E для всех k в i через j — 1. Простой путь — это путь, в котором ни одна вершина не появляется более одного раза.
Пусть A будет массивом nxn, инициализированным следующим образом

 

Рассмотрим следующий алгоритм.

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

Какое из следующих утверждений обязательно верно для всех j и k после окончания вышеуказанного алгоритма?
(A) A [j, k] ≤ n
(B) Если A [j, k] ≥ n — 1, то G имеет гамильтонов цикл
(C) Если существует путь от j до k, A [j, k] содержит самый длинный путь линзы от j до k
(D) Если существует путь от j до k, каждый простой путь от j до k содержит большинство A [j, k] ребер

Ответ: (D)
Объяснение:

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.

Тест на этот вопрос

Рекомендуемые посты:

ВОРОТА | GATE-CS-2003 | Вопрос 70

0.00 (0%) 0 votes