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

4.  Препарата Ф., Шеймос М. Вычислительная геометрия: Введение. .-М.: Мир, 1989.

5.  Гнеденко Б.В., Коваленко И.Н. Введение в теорию массового обслуживания. –М.: 1987.

6.  Адельсон-Вельский Г.М., Донской Е.А., Карзанов А.В. Потоковые алгоритмы. .-М.: Наука, 1975.

7.  Кристофидес Н. Теория графов. Алгоритмический подход.-М.: Мир, 1978.

8.  Кормен Т., Лейзерсон Ч., Ривест Р. Алгоритмы: построение и анализ. .-М.: МЦНМО, 2001.

9.  Поддерюгин В.Д. Алгоритм определения реберной связности графа. – Сб. «Вопросы кибернетики. Труды семинара по комбинаторной математике (Москва, 1971)». М., «Советское радио», 1973.

Адельсон-Вельский Георгий Максимович, Донской Ефим Абрамович, Карзанов Александр Викторович.

Пример 3:

Этап 1:           ОЧИСТКА слоя 2.                ОЧИСТКА слоя 1.

Осталась цепочка

minПСВ=4, F=4

Этап 2:

k=7; f=minПСВ=3; F=7

k=2; f=3, F=10, вхПСВ(4)-4=5          k=4; f=1, F=11, выхПСВ(1)-4=6            f=6, F=17

Этап 3:                                                                       ОЧИСТКА слоев 4 и 3:

k=7, f=1; F=18

k=3,  f=2; F=20                              f=2, F=22

Этап 4:

f=1, F=23

Этап 5:

Максимальный поток F(X) = 23 и минимальный разрез a(R)=23.
По ребру (2,4) на этапе 2 течет поток f₂₄ = 3, а на этапе 4 навстречу – f₄₂ = 1.

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

      макрограф

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

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

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

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

6.  Для всех вершин находим ближайшую вершину BV и строим симметричное замыкание BV: если BV(i)=j и BV(j) ≠ i, то в BV(j) добавляем i. В замыкании будет не более (n-1) неориен.ребра.

7.  Поиском сначала вширь по массиву BV выделяем компоненты связности.
           I:   1,2,3            II:   4,7            III:  5,8,6     IV:   9,10

Трудоемкость этой части = числу ребер в симметрическом замыкании < 2n.

8.  ОЧИСТКА. Формируем ребра макрографа в виде списков соседних компонент связности. Если в списке соседей очередной вершины i встретится вершина j из другой компоненты k, то запишем в список соседних макровершин блок ^k/_d (i, j), где d – длина кратчайшего из ребер между вершинами компонент.