Задачи для самостоятельного решения

↑

⇐ ПредыдущаяСтр 5 из 11Следующая ⇒

Задачи для самостоятельного решения

1. В следующих сетях найти максимальный поток из источника s в сток t и сответствующий минимальный разрез.

a)

b)

с)

d)

2. Найти максимальный поток из источника s в сток t и сответствующий минимальный разрез при заданных пропускных способностях для некоторых вершин (указаны в кружочках).

b)

3.В следующих сетях найти максимальный поток из источников в стоки и сответствующий минимальный разрез.

a)

b)

4. В следующих примерах на дугах первой цифрой указана нижняя граница пропускной способности, второй − верхняя граница пропускной способности. Найти максимальный поток из источника s в сток t или показать, что поток не существует.

a)

b)

3.2. Задача о многополюсном максимальном потоке

Пусть дана неориентированная сеть  с пропускными способностями ребер  ≥ 0, (x, y)ÎE. Задача о многополюсном максимальном потоке состоит в поиске максимального потока для всех пар вершин данной неориентированной сети. Для ее решения можно заменить ребра парами противоположно направленных дуг и применить алгоритм Форда-Фалкерсона для каждой пары вершин. При этом общее число задач о максимальном потоке, которые необходимо будет решить, равно n(n-1)/2 (n = |V |).  Более эффективным методом, в котором задача о максимальном потоке решается n-1 раз,  является алгоритм Гомори-Ху.

Для описания алгоритма введем следующую операцию над вершинами сети. Пусть S Í V. Конденсацией множества вершин S назовем замену S одной вершиной {S}, с сохранением в сети всех ребер (x, y) Î E, для которых x, y Î V \ S, и их пропускных способностей, и замещением для каждой вершины y Î V \ S, всех ребер  (x, y) Î E, для которых x Î S, одним ребром (s, y), с пропускной способностью равной сумме пропускных способностей замещаемых ребер.

Построим на множестве вершин исходной сети полный неориентированный граф G^’ = (V, E^’ ) и положим вес ребра (x, y) Î E^’ равным n (x, y) пропускной способности минимального разреза отделяющего x от y в исходной сети (эквивалентно, величине максимального потока между x и y). Пусть G ^“ = (V, E ^“ ) максимальное остовное дерево для G^’ = (V, E^’ ). Если x, u₁, u₂, … , u_k, y единственный путь в G ^“ = (V, E ^“ ) от x к y, то в силу максимальности остовного дерева,

n (x, y) £ min [ n ( x, u₁), n ( u₁, u₂), … , n ( u_k, y ) ].

С другой стороны, из свойств минимального разреза, получим

n (x, y) ≥ min [n ( x, u₁), n ( u₁, u₂), … , n ( u_k, y )].

Следовательно,  

n (x, y) = min [n ( x, u₁), n ( u₁, u₂), … , n ( u_k, y)].

Идея алгоритма Гомори-Ху состоит в итеративном построении максимального остовного дерева G ^“ = (V, E ^“ ). Если требуется определить величину макси­мального потока между двумя произвольными узлами, надо в дереве найти путь, соединяющий эти два узла, и выбрать в этом пути дугу с минимальным весом. Вес этой дуги равен величине максимального потока между рассматриваемыми узлами.

Алгоритм Гомори-Ху. Шаг 1. В качестве множества ребер E^” дерева выбрать пустое множество. Объединить все узлы в одно множество-вершину {U} = {V }.

Шаг 2. k=1. Выбрать произвольную пару узлов s и t.

Шаг 3. Определить максимальный поток из s в t с помощью алгоритма Форда-Фалкерсона

Шаг 4. Найти минимальный разрез , отделяющий s от t.  Разбить множество-вершину {U}, которой принадлежат s и t, на два множества-вершин {U₁}, {U₂} отнеся к первой вершины из {U}, принадлежащие S, ко второй – вершины из {U} не принадлежащие S .  Данный разрез представить ребром ({U₁}, {U₂}) и поместить в дерево. Вес ребра положить равным пропускной способности минимального разреза. Ребро ({X}, {U})Î E^” текущего дерева, заменяем ребром ({X}, {U₁}),  если X Í S, и ребром  ({U₂}, {X}), если X Í .

Шаг 5. Если k = n-1, то закончить работу алгоритма. В противном случае, перейти к шагу 6.

Шаг 6. Выбрать произвольную пару узлов x и y, принадлежащих некоторому множеству-вершине {U}, то есть еще не отделенных друг от друга ребром в строящемся дереве. Положить s = x и t = y.

Шаг 7. Сконденсировать в один узел каждую связную ветвь дерева, соединенную с множеством-вершиной {U}. Перейти к шагу 3.

Пример. Для следующей сети найти максимальный поток между каждой парой вершин.

Итерация 1. Возьмем s = x₁, t = x₈ . Минимальный разрез, отделяющий x₁ от x₈, есть <{x₁, x₂, x₃, x₄ }, {x₅, x₆, x₇, x₈ } >.  Его пропускная способность равна n (x₁, x₈) = 6. По минимальному разрезу получим, что дерево на первой итерации состоит из двух множеств-вершин: {x₁, x₂, x₃, x₄}, {x₅, x₆, x₇, x₈ } и единственного ребра с весом равным 6 (рис. 6).

Рис. 6. Первая итерация алгоритма Гомори-Ху

Итерация 2. Берем вершины, принадлежащие одному множеству-вершине, например s = x₁, t = x₄ . В исходной сети конденсируем множество вершин {x₅, x₆, x₇, x₈ }, как принадлежащее одной связной ветви текущего дерева. В результате получим сеть, представленную на рис. 7.

Рис. 7. Вторая итерация алгоритма Гомори-Ху

Минимальный разрез, отделяющий x₁ от x₄, есть <{x₁, x₂, x₃, {x₅, x₆, x₇, x₈}}, {x₄} >.  Его пропускная способность равна n (x₁, x₄) = 4. По минимальному разрезу получим, что дерево на второй итерации состоит из множеств-вершин: {x₄}, {x₁, x₂, x₃}, {x₅, x₆, x₇, x₈ } и ребер с весами равными 4 и 6 (рис. 7).

Итерация 3. Возьмем s = x₅, t = x₈ . В исходной сети конденсируем множество вершин {x₁, x₂, x₃, x₄ }, как принадлежащее одной связной ветви текущего дерева. В результате получим сеть, представленную на рис. 8. Минимальный разрез, отделяющий x₅ от x₈, есть <{{x₅}, {x₆, x₇, x₈}, {x₁, x₂, x₃, x₄ }} >.  Его пропускная способность равна n (x₅, x₈) = 6. По минимальному разрезу получим, что дерево на третьей итерации состоит из множеств-вершин: {x₄}, {x₁, x₂, x₃}, {x₆, x₇, x₈ }, { x₅} и ребер с весами равными 4, 6, 6 (рис. 8).

Рис. 8. Третья итерация алгоритма Гомори-Ху

Итерация 4. Возьмем s = x₁, t = x₂. В исходной сети конденсируем множество вершин {x₅, x₆, x₇, x₈}, как принадлежащее одной связной ветви текущего дерева. В результате получим сеть, представленную на рис. 9. Минимальный разрез, отделяющий x₁ от x₂, есть <{x₁}, {x₂, x₃, x₄ , {x₅, x₆, x₇, x₈ }} >.  Его пропускная способность равна n (x₁, x₂) = 10. По минимальному разрезу получим, что дерево на четвертой итерации состоит из множеств-вершин: {x₄}, {x₁}, {x₂, x₃}, {x₆, x₇, x₈ }, { x₅} и ребер с весами равными 4, 10, 6, 6 (рис. 9).

Итерация 5. Возьмем s = x₂, t = x₃ . Получим сеть, представленную на рис. 10. Минимальный разрез, отделяющий x₂ от x₃, есть <{x₂},  {x₁, x₃, x₄ , {x₅, x₆, x₇, x₈ }} >.  Его пропускная способность равна n (x₁, x₂) = 11. По минимальному разрезу получим, что дерево на пятой итерации состоит из множеств-вершин: {x₄}, {x₁}, {x₂}, {x₃}, {x₆, x₇, x₈ }, { x₅} и ребер с весами равными 4, 10, 11, 6, 6 (рис. 10).

Рис. 9. Четвертая итерация алгоритма Гомори-Ху

Рис. 10. Пятая итерация алгоритма Гомори-Ху.

Рис. 11. Шестая итерация алгоритма Гомори-Ху

Рис. 12. Седьмая итерация алгоритма Гомори-Ху

Итерация 6. Возьмем s = x₆, t = x₇ . Получим сеть, представленную на рис. 11. Минимальный разрез, отделяющий x₆ от x₇, есть <{x₇},  {{x₁, x₂,  x₃, x₄} , x₅, x₆, x₈ }} >.  Его пропускная способность равна n (x₁, x₂) = 9. По минимальному разрезу получим, что дерево на пятой итерации состоит из множеств-вершин: {x₄}, {x₁}, {x₂}, {x₃}, {x₇}, {x₆, x₈}, { x₅} и ребер с весами равными 4, 10, 11, 9, 6, 6 (рис. 11).

Итерация 7. s = x₆, t = x₈ . Получим сеть, представленную на рис. 12. Минимальный разрез, отделяющий x₆ от x₈, есть < {{x₁, x₂,  x₃, x₄} , x₅, x₆, x₇ }}, {x₈}>.  Его пропускная способность равна n (x₁, x₂) = 10. По минимальному разрезу получим, что дерево на седьмой итерации состоит из вершин x₁, x₂,  x₃, x₄, x₅, x₆, x₇, x₈ и ребер с весами равными 4, 10, 10, 11, 9, 6, 6 (рис. 12). Дерево стало полным, и алгоритм завершает работу.

Для определения величины максимального потока, например, между вершинами x₂, x₇, находим единственный путь, соединяющий эти вершины в результирующем дереве. Это путь ( x₂, x₃ ), ( x₃, x₆ ), ( x₆, x₇ ). Ребро с минимальным весом   ( x₃, x₆ ). Следовательно, искомый поток равен 6.

Познавательные статьи:



Где возникла философия и почему?

Относительная высота сжатой зоны бетона

Сущность проекции Гаусса-Крюгера и использование ее в геодезии

Тарифы на перевозку пассажиров