График и алгоритм

Question

Пусть G (V, E) - ориентированный граф с n вершинами.Путь от vi до vj в G является последовательностью вершин (vi, vi+1, ……., vj) такой, что (vk, vk+1) ∈ E для всех k в i до j – 1.

Простой путь - это путь, в котором ни одна вершина не появляется более одного раза.

Пусть A будет массивом n x n, инициализированным следующим образом

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

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

Я не могу начать, как решить эту проблему. Пожалуйста, помогите.

Вопрос былспросил тот, который является правильным вариантом -

(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] ребер

Я понимаю, люди здесь не решают вопросы, но этот вопросЯ поступил на вступительный экзамен для получения степени магистра в CS, и я не могу придумать, с чего начать, и если бы кто-то просто дал мне график и некоторые указатели, которые были бы действительно потрясающими.

*

PS - правильный вариант ответа (d)

*

Answer 1

(A) A [j, k] ≤ n

Нет, посмотрите на пример счетчика:

1 1
1 1 

1,1,1:
A[1,1] = 2
1,1,2:
A[1,2] = 2
1,2,1:
A[2,1] = 3
(Rest is redundant)

(B) ЕслиA [j, k] ≥ n - 1, то G имеет гамильтонов цикл.

Это предполагает P = NP, поскольку нахождение гамильтонова цикла является NP Hard.

(C) Если существует путь от j до k, A [j, k] содержит самую длинную линзу от j до k.

Опять же, это будет означать P = NP, потому чтоВы можете легко использовать его, чтобы найти гамильтоновы пути, если таковые существуют.

(D) Если существует путь от j до k, каждый простой путь от j до k содержит большинство A [j, k]dge

Это верно по индукции, если вы предполагаете, что гипотеза верна, и это число никогда не будет меньше числа ребер в простом пути, функция max {} гарантирует, что высохраняйте самое высокое значение, и по предположению индукции, A [j, i], A [i, k] каждый больше, чем число ребер в простых путях, и, таким образом, их сумма больше, чем любой простой путь, который использует thПуть, основанный на них.