Теория игр и исследование операций. Модели, алгоритмы, сложность: Конспект лекций, страница 29

Результат зависит от нумерации вершин. Что значат числа в полученной матрице? После 1-го шага – это длины либо прямых путей, либо двузвенных (через 1 вершину?). После 2-го шага число разрешенных звеньев увеличивается до 4, после 3-го шага – до 8. В результате получим путь длины 2 через 1-ю вершину: 2(1)+2(2)+2(3)+3(1 2)+3(1 3)+3(2 3)+4(1 2 1)+4(1 3 1)+4(2 3 2)+8(1 2 1 3 1 2 1)+… +7(…)+… +6(…)+…+5(…)+… В цепочках не участвует только вершина 4 (на 3-ем шаге).

С каждой матрицей можно связать списки вершин. Например: S₂= (0,1,2,12, 121).

S₃={(v3u): v, uÎS₂}, | S ₂| = 6 ´ 6, | S ₃| = 36 ´ 36- мощность S₃.???

Нахождение кратчайшего пути для ациклического орграфа

Утверждение 1: В ациклическом графе существует вершина, в которую не входит ни одна дуга.

Доказательство. Предположим противное. Возьмем любую вершину. По предположению в нее входит дуга. Перейдем в начало дуги, пометив его и т.д. Число вершин конечно Þ когда-то мы попадем в помеченную вершину и найдем цикл.

Вершины, в которые не входит ни одна дуга, поместим на слой 1 и удалим выходящие из них дуги. В оставшемся графе снова возьмем вершины, в которые не входят дуги, поместим их на слой 2 и восстановим входящие в них дуги с предыдущих слоев и т.д.

Обработаем этот граф:     D(1)=0     D(2)=d₁₂+D(1)=3,         D(4)=d₂₄+D(2)=-1+3=+2,

D(5)=d₂₅+D(2)=-5+3=-2, D(3)= min{d₄₃+D(4), d₁₃+D(1)}=-4, D(6)= min{D(4)+4, D(3)+9, D(5)+2}=0. Кратчайший путь легко строится по вектору отцов.

Алгоритм работает для любого ациклического графа. Оценим его трудоемкость:

1.  построение слоистой сети ~ числу дуг этого графа

2.  è трудоемкость алгоритма ~ числу дуг, каждая дуга будет обработана 1 раз

В слоистой сети и в начальном графе число дуг совпадает.

№22. Задача сетевого планирования.

Дано множество работ {r_k} с длительностями t_kи отношение предшествования Pмежду работами. Найти минимальное время, за которое можно выполнить все работы.