Пример задачи о многополюсном максимальном потоке

Рассмотрим сеть изображенную на рисунке п1.4. Числа, приписанные дугам, соответствуют их пропускным способностям. Требуется для каждой пары узлов сети определить величину максимального потока между ними.

Рис.п1.4. Сеть в задаче о многополюсном максимальном потоке.

Данная задача решается за интеграций алгоритма Гомори – Ху. Если процедура расстановки пометок поменялась бы к каждой паре узлов, то потребовалось бы решить 21 задачу о максимальном потоке. Разрезы, построенные на каждой итерации, состоят из дуг, остаточная пропускная способность которых равна нулю. Для простоты изложения мы опустили результаты, полученные при выполнении процедур расстановки пометок.

Итерация 1. Рассмотрим узлы s=2 и t=5. Величина максимального потока равна 13. Поэтому . По разрезу с минимальной пропускной способностью мы определяем, что построение дерева разрезов можно начать с ветви, соединяющей узел 5 и конденсированные узел, состоящий из узлов 1, 2, 3, 4, 6, 7 (рис п1.4а). Вес данной ветви равен 13.

Рис.п1.4а. Задача о максимальном потоке: первая итерация.

Итерация 2. Рассмотрим узлы s=1 и t=2. Величина максимального потока

равна 19. Поэтому . По минимальному разрезу мы определяем, что узлы 2 и 5 лежат по одну его сторону, а все остальные узлы сети – по другую сторону этого разреза (рис.п1.4б). Вес ветви, соединяющий узел 2 и конденсированный узел, состоящий из узлов 1, 3, 4, 6 и 7, равен 19.

Рис.п1.4б. Вторая итерация.

Итерация 3. Рассмотрим узлы 6 и 7. Величина максимального потока

Равна 21. Поэтому . По минимальному разрезу мы определяем, что узел 7 в дереве разрезов соединяется с конденсированным узлом, состоящим из узлов 1, 3, 4, 6, дугой, вес которой равен 21. Кроме того, узлы 2 и 5 и конденсированный узел(1, 3, 4, 6) расположены по одну сторону минимального разреза, а узел 7 – по другую сторону этого разреза (рис.п1.4в).

Рис.п1.4в. Третья итерация.

Итерация 4. Рассмотрим узлы s=4 и t=6. Величина максимального потока

равна 25. Поэтому . По минимальному разрезу видно, что узлы 6 и 7 расположены в той же части дерева разрезов, что и узел (1, 3, 4) (рис.п1.4г).

Рис.п1.4г.Четвертая итерация.

Итерация 5. Рассмотрим узлы s=1 и t=4. Величина максимального потока равна 24. Поэтому . Определяя минимальный разрез, удаляем узел 1 из узла (1, 3, 4) и располагаем его по ту сторону узла (3, 4), где не находится ни один из оставшихся узлов (рис.п1.4д). Вес соответствующей дуги в дереве разрезов равен 24.

Рис.п1.4д. Пятая итерация.

Итерация 6. Рассмотрим узлы s=3 и t=4. Величина максимального потока равна 22. Поэтому . Найдя минимальный разрез, удаляем узел 3 из узла (3, 4) и соединяем его с узлом 4 дугой дерева разрезов, вес которой равен 22. Теперь дерево разрезов стало полным, т.е. состоит из шести дуг. Поэтому процедура заканчивается (рис.3.4е).

Рис.п1.4е. Шестая итерация.

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

Приложение 2

Задача об остовном дереве

Перед тем как перейти к изучению этой новой потоковой задачи, остановимся на определениях, которые имеют непосредственное отношение к нахождению доминирующего остовного дерева.

Назовем деревом связное множество неориентированных ре­бер (дуг), не содержащее циклов. Таким образом, если задано множество т узлов, соединенных неориентированными ребра­ми, то для построения дерева необходимо выделить подмноже­ство, состоящее из т—1 дуги. Иными словами, каждый узел соединен с другим узлом одним-единственным путем.

Рассмотрим сеть, содержащую п узлов, совокупность кото­рых образует множество S.Остовным деревом называется связ­ное множество, состоящее из (п—1) дуг (ребер) и п узлов. Из любого собственного подмножества множества S может быть образовано дерево. Будем предпо­лагать, что каждой дуге, соединяющей узлы i и j из множества S, приписано число с_ij, называемое расстоянием, или весом, ду­ги. Теперь мы можем ввести понятие максимального доминирующего остова. Доминирующим остовом называется такой остов сети, у которого сумма весов с_ij всех его дуг максимальна.

Построение доминирующего остова встречается в задачах синтеза структуры сети по методу Гомори-Ху.

Алгоритм построения доминирующего остова

Шаг 1. Используя узлы исходной сети, определить следующие два множества: S — множество соединенных узлов; — мно­жество несоединенных узлов. Вначале все узлы будут принад­лежать множеству . Шаг 2. Выбрать произвольный узел из и соединить его с ближайшим соседним узлом дугой максимального веса. (После выполнения данного шага множество S будет содержать два узла.)

Шаг 3. Среди всех дуг, соединяющих узлы из множества S с узлами из множества , выбрать дугу максимального веса. Концевой узел этой дуги, лежащий в S, обозначить через б. Удалить узел б из множества и поместить его в множество S.

Шаг 4. Выполнять шаг 3 до тех пор, пока все узлы не будут принадлежать множеству S.

Пример решения задачи из главы 9

Построить остовное дерево доминирующих потоков для ниже приведенной сети (рис.11.3)

Рис.П.2.1. Пример сети в задаче о кратчайшем остове

Шаг 1. = (1, 2, 3, 4, 5, 6, 7), S = 0.

Шаг 2. Выбрать узел 6. Соединим дугой максимального веса с узлом 7

S = (6, 7) Стоимость = 7 ед.

= (1,2,3,4,5).

Шаг 3.

а) Выбрать узел 5. S= (6, 7, 5), = (I, 2, 3, 4).

б) Выбрать узел 2. S= (6, 7, 5,2), = (I, 3, 4)

в) выбрать узел 3. S= (6, 7, 5, 2, 3), = (I, 4).

г) выбрать узел 1. S= (6, 7, 5, 2, 3, 1), = (4).

д) Выбрать узел 4. S= (6, 7, 5, 2, 3, 1, 4), = 0.

ПРИМЕНЕНИЯ ЗАДАЧИ О КРАТЧАЙШЕМ ОСТОВЕ

Задача о кратчайшем остове (ЗКО) находит широкое прак­тическое применение. Многие задачи, на первый взгляд не по­хожие на ЗКО, после некоторых преобразований сводятся к ней. С помощью построения кратчайшего остова, например, Д. Росси, Хейзер и Кинг, предложили схему прокладки те­левизионных кабелей, соединяющих все станции в единую сеть. Но наиболее интересное и важное применение ЗКО, по-види­мому, находит в кластерном анализе, где ряд задач, решающихся другими методами этого анализа, наиболее эффективно решаются с помощью построения КО. Другое применение ЗКО находит при оценке надежности сетей: вес КО соответст­вует минимальной вероятности того, что дерево будет повреж­дено в одной или нескольких дугах. Гомори и Ху, исполь­зовали алгоритм построения КО при решении задач о много­полюсных потоках. Хелд и Карп, нашли аналогичное применение ЗКО для решения задачи коммивояжера.

Приложение 3.

Дата добавления: 2014-01-07