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

N<n, но искать min не по чему, т.к. O(j)=0 для всех невключенных вершин Þ ребер между включенными и невключенными вершинами нет Þ граф несвязен. Мы построили МОД одной компоненты связности: D_мод=2+1+1+2+2+1+1=10.

Описание алгоритма Прима:

Шаг 0: Инициализация (Если не 0, то пишем в таблицу, если =0, то не пишем)

a)  W(1) = O(1) = 1, W(i)=O(i)=0 " i >1

b)  " i Î S(1) : O(i)=1, D(i)=d(1,i)

Можно считать, что граф полный. Если ребра (i,j) нет, то d(i,j) = ∞. Или для всех вершин должны быть заданы списки S(i) номеров соседних с i вершин.

Основной шаг:

a)  k = argmin D(i), где iÎW^-1(0) Ç O^-1(>0) , т.е. W (i) = 0 & O (i) ¹ 0.

т.е. берем минимум по «видимым» вершинам. Если таких вершин нет, но пройдены не все вершины, то выход: граф не связен; если пройдены все вершины, то выход: кратчайшее остовное дерево (нормальное завершение)

b)  W(k)=1 – включить эту вершину

c)  " j Î S(k) & W_j = 0 : O(j)=0 или D(j)>d(k,j)èкоррекция: O(j)=k и D(j)=d(k,j).

Число основных шагов должно быть равно n-1, если пройдем по всем вершинам.

Остовное дерево состоит из ребер (i,O(i)).

Трудоемкость алгоритма Прима: (волновой алгоритм)

Корректность алгоритма Прима.

Каждый раз подключается новая вершина Þ строится связный граф без циклов и с n-1 ребром Þ алгоритм Прима строит дерево. Почему это МОД?

Утверждение:d(G₀)=d(G₁), где G₀-дерево, построенное алгоритмом Прима, G₁-МОД.

Доказательство. Множества вершин в G₀= (V, E₀) и G₁= (V, E₁) совпадают. Пронумеруем вершины и ребра G₀ в порядке их включения алгоритмом Прима.

У каждой вершины только один сосед в G₀ с меньшим номером – «отец»!

Введем целочисленное расстояние

Пусть E₀¹ E₁. Выберем ребро e = (n₁, n₂)ÎE₀\ E₁ с минимальным номером. Пусть n₁<n₂. Ребра G₁ не нумерованы. Пойдем по ним от вершины n₁ к n₂, пока впервые не встретим такое ребро l = (n₃, n₄), что n₃<n₂≤n_4.

1.  n₂=n₄ Þ lÏ E₀, иначе n₂ имеет в G₀ двух соседей n₁,n₃ < n₂.

2.  n₂<n₄ Þ если lÎ E₀, то номер ребраl больше номера ребра e.

В любом случае граф G₂= (V, E₁ + e - l) является деревом и ρ (G₀,G₂) < ρ (G₀,G₁) (число ребер = n-1, при добавлении ребра e появился цикл, а при удалении ребраl из цикла связность не нарушится, min номер ребра в E₀\ E₁ увеличивается).

Ребра e,l ÎR (W) на шаге n₂ и алгоритм Прима выбрал ребро e Þ d(e) ≤ d(l) Þ d(G₂) ≤ d(G₁). Но G₁ – МОД. Поэтому d(G₂)=d(G₁). Þ G₂ – тоже МОД.

Повторим в цикле выбор ребер e и l и переход от G_k к G_k+1. На каждом шаге ρ (G_k,G₁) убывает по крайней мере на 1 и не позже, чем через n-1 шаг будет =0, т.е. деревья G₀ и G_k совпадут. Получили цепочку: d(G_k= G₀) = … = d(G₁).

Пример. На шаге n₂=7 вершины n₁=2 и n₃=5 будут включены, а n₂ и n₄=9 нет.

№20. Алгоритм Тарьяна (для планарных графов МОД строится за O(n)).

      макрограф

тоже планарный

Этап 1.                                           Этап 2.

На каждом шаге число операций ≈ числу дуг=2R<6n

1.  Формируем списки соседей всех вершин.