Максимальные потоки.

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

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

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

Особенностью сети является наличие вершины-истока и вершины-стока, ориентация всех отрезков линий в графе и отсутствие петель и кратных дуг.

Объем информации, энергии или вещества, передаваемый в сети от узла x i к узлу x j , называют потоком и обозначают j ij .

Наибольший поток, который может пропустить дуга (x i , x j), называют пропускной способностью дуги и обозначают с ij .

Очевидно, что 0£j ij £ с ij .

В вершине-истоке х 0 величина потока есть сумма потоков по всем дугам, исходящим из вершины х 0 , т.е. j=å i j 0i + .

В вершине-стоке х k величина потока есть сумма потоков по всем дугам, заходящим в вершину х k , т.е. j=å i j ik - .

Для любой промежуточной вершины х i сумма исходящих потоков равна сумме заходящих потоков, т.е. å j j ij + =å k j ik - .

На рис. 3.29 показана условная сеть, содержащая вершину-исток х 0 , вершину-сток х k и две промежуточные вершины х i и х j . На каждой дуге в круглых скобках приведены обозначения потока и пропускной способности соответствующей дуги. При этом поток, подводимый к сети равен j=(j 0i +j 0j), поток отводимый от сети равен j=(j ik +j jk), поток из вершины х i в вершину х j равен j ij . Для вершины х i имеем j 0i =(j ij +j ik), для вершину х j - j jk =(j 0j +j ij).

Если множество вершин графа разбить на два непересекающихся подмножества, одно из которых содержит вершину-исток, а другое - вершину-сток, то множество дуг, соединяющих эти два множества, формируют разрез А i , пропускная способность которого равна сумме пропускных способностей дуг. Таких разрезов может быть несколько.

В таблице приведены четыре разреза для сети на рис. 3.29

Разрез	пропускная способность дуги Сij	пропускная способность
	С 0 i	С 0 j	С i j	С i k	С jk	разреза С(A i)
А 1						С 0i + С 0j
А 2						С 0j +С ij +С ik
А 3						С ik +С jk
А 4						С 0i +С ij +С jk

Например, для разреза А 1 имеем Х’={x 0 } и X\Х’={х i , х j , х k }, для А 2 - Х’={х 0 , х i } и X\Х’={х j , х k }, для А 3 - Х’={х 0 , х i , x j } и X\Х’={х k }, для А 4 - Х’={х 0 , х j } и X\Х’={x i , х k }.

Очевидно, что величина максимального потока ограничена минимальной пропускной способностью разреза, т.е.

j max =min{С(A i)}

Итак, максимальный поток в сети с заданными пропускными способностями дуг можно находить, вычисляя пропускные способности разрезов и выбирая среди них - минимальную. Однако при таком решении остается неизвестным распределение потока по дугам.

Для поиска распределения потока по дугам разработано несколько алгоритмов. Особое место среди них занимает алгоритм Форда-Фалкерсона, суть которого состоит в разметке вершин графа.

Метка вершины графа указывает на возможность изменения потока через данную вершину и указывает источник этого изменения. На рис. 3.30 дан фрагмент сети, объясняющий суть алгоритма.

Если по дуге (х s , х i) возможно увеличение потока (j si < c si), то вершину х i следует пометить +s , что указывает на источник увеличения потока.

Если по дуге (х i , х j) возможно увеличение потока j ij < c ij , то вершину х j пометить +i . Это означает, что приращение потока Dj si пойдет по направлению дуги (х i , х j) от вершины х s .

Если насыщена дуга (х s , х i), т.е. j si =c si , то метку +s нельзя ставить у вершины х i . Следовательно, если вершина x i не помечена, то у вершины x j нельзя ставить метку +i.

Если по дуге (х t , х j) возможно увеличение потока, т.е. j tj < c tj , то вершину х j следует пометить +t , что указывает на источник увеличения потока.

Если вершина х j не имеет пометки +i , то для увеличения потока в фрагменте сети, следует уменьшить поток в дуге (х i , х j) и направить его далее по другим дугам фрагмента на сток. Для указания этого у вершины x i ставят метку – j. Это означает что при общем приращении потока на участке (х i , х j) он должен быть уменьшен на величину Dj tj .

Если насыщена дуга (х t , х j), т.е. j tj =c tj , то метку +t нельзя ставить у вершины х j . Следовательно, если вершина x j не помечена, то у вершины x i нельзя ставить метку -j.

Если насыщены обе дуги (х s , х i) и (х t , х j), что означает невозможность приращения потока Dj si и Dj tj , то нельзя ставить метки у вершин x i и x j и продолжения разметки следующих вершин сети до вершины-стока.

Так достигают максимального значения потока от вершин-истоков х s и х t по дугам к вершинам - стокам х i и х j .

Алгоритм Форда-Фалкерсона:

шаг 1 : присвоить всем вершинам графа индексы 0,1,2,...k; где 0-индекс вершины-истока графа, k -индекс вершины-стока графа;

шаг 2 : присвоить начальной вершине метку “0”;

шаг 3 : все непомеченные вершины х i , в которые идут ненасыщенные дуги из помеченной вершины х s , пометить индексом “+s”, что свидетельствует о возможности увеличения потока из вершины х s по дуге (х s , х i);

шаг 4 : все непомеченные вершины х i , из которых идут дуги (насыщенные или ненасыщенные) в помеченную вершину х j , пометить индексом “-j”, что свидетельствует о возможности уменьшения потока в вершину х j по дуге (х i , х j);

шаг 5 : если в результате этих операций окажется помеченной вершина-сток x k , то между начальной и конечной вершинами сети найдется маршрут, все вершины которого различны и с точностью до знака помечены индексами предыдущих вершин, формирующих переход, по которому можно увеличить поток, и перейти к шагу 6, иначе конец.

шаг 6 : увеличить поток в маршруте, сформированном на шаге 5, на единицу и перейти к шагу 3.

Признаком окончания работы алгоритма является невозможность пометки вершины-стока.

Пример : На рис. 3.31 дан граф. Найти величину максимального потока и его распределение в сети.

На каждой дуге (х i , х j) указаны величина потока и пропускная способность - (j ij , c ij).

Все расчеты сведены в две таблицы таблица а)

х i	шаг итерации

х 0
х 1	+0	+0	+0	+0, -3	-3	-	-
х 2	+0;+3	+0;+3	+0	+0	+0	+0	-
х 3	+0;+1	+0;+1	+0;+1	+0	+0	-	-
х k	+1;+2;+3	+1;+2	+1;+2	+1;+2	+1,+2	+2	-

таблица b)

(х i , х j)	С ij	шаг итерации

(х 0 , х 1)
(х 0 , х 2)
(х 0 , х 3)
(х 1 , х 3)
(х 1 , х k)
(х 2 , х k)
(х 3 , х 2)
(х 3 , х k)

В таблице а) на каждом шаге итерации для каждой вершины графа указаны возможные метки, а в таблице b) даны приращения потока по дугам (х i , х j). Полужирным шрифтом выделены насыщенные дуги графа

В результате выполнения первого шага итерации возможны переходы: n 0k ={(х k , х 1 , х 0); (х k , х 2 , х 0); (х k , х 2 , х 3 , х 0); (х k , х 2 , х 3 , х 1 , х 0);

(х k , х 3 , х 0); (х k , х 3 , х 1 , х 0)}. Пусть выбран n 0k =(х k , х 3 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((х 0 , х 3), (х 3 , х k)).

На втором шаге возможны те же переходы. Пусть выбран переход n 0k =(х k , х 3 , х 0). Приращение потока на Dj=1 проходит по маршруту m={(х 0 , х 3), (х 3 , х k)}. При этом дуга (х 3 , х k) оказывается насыщенной, т. е. j 3k =c 3k =2.

На третьем шага возможны переходы: n 0k ={(х k , х 1 , х 0); (х k , х 2 , х 0); (х k , х 2 , х 3 , х 0); (х k , х 2 , х 3 , х 1 , х 0)}. Пусть выбран n 0k =(х k , х 2 , х 3 , х 1 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 1), (x 1 , x 3), (x 3 , x 2), (x 2 , x k)). При этом оказывается насыщенной дуга (х 3 , х 2), т. е. j 32 =c 32 =1.

На четвертом шаге возможны переходы: n 0k ={(х k , х 1 , х 0); (х k , х 2 , х 0)}. Пусть выбран n ok =(х k , х 1 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 1), (x 1 , x k)),. При этом оказывается насыщенной дуга (х 0 , х 1), т. е. j 01 =c 01 =2.

На пятом шаге возможны переходы: n 0k ={(х k , х 1 , -x 3 , х 0); (х k , х 2 , х 0)}. Пусть выбран n ok =(х k , х 1 , -x 3 , х 0). Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 3), (x 3 , x 1), (x 1 , x k))),. При этом оказывается насыщенной дуга (х 0 , х 3), т. е. j 03 =c 03 =3.

На шестом шаге возможен только один переход n 0k =(х k , х 2 , х 0), так как дуги (x 0 , x 1) и (x 0 , x 3) насыщены. Приращение потока на Dj=1 проходит по маршруту m=((x 0 , x 2), (x 2 , x k)),. При этом оказывается насыщенной дуга (х 0 , х 2), т. е. j 02 =c 02 =1.

На седьмом шаге невозможны ни один переход от x o к x k , так как дуги (x 0 , x 1), (x 0 , x 3) и (х 0 , х 2) насыщены и невозможно поставить метки у вершин x 1 , x 2 , и x 3 .

Транспортная задача
Может возникать в физике, экономике и т.д.
На отдельные компоненты транспортной сети
(сеть железнодорожных, автомобильных и т.д.
путей; сеть трубопроводов и т.д.) наложены
ограничения – их максимально допустимая
нагрузка.
Необходимо определить максимально
возможное количество пассажиров, товара,
продукта и т.д., которое можно провезти по этой
сети и каким образом.
Мы построим графовую дискретную модель
этой транспортной задачи и решим ее в этой
модели.

Математик Джордж Бернард Данциг, с 1941 года
работая в отделе статистического управления Военновоздушных сил США в Вашингтоне, впервые решил
задачу о максимальном потоке в ходе подготовки
воздушного моста во время блокады Западного Берлина.
В 1951 году Джордж Данциг впервые сформулировал
задачу в общем виде. В 1955 году, Лестер Форд и
Делберт Фалкерсон впервые построили алгоритм,
специально предназначенный для решения этой задачи.
Их алгоритм получил название алгоритм ФордаФалкерсона.
В 2010 году исследователи Джонатан Кёлнер и
Александер Мондры из МТИ вместе со своими
коллегами Дэниелем Спилманом из Йельского
университета и Шень-Хуа Тенем из ЮжноКалифорнийского университета продемонстрировали
очередное улучшение алгоритма.

Дан ориентированный граф
(транспортная сеть) G=(V, E), вершина
графа s (источник) и вершина t (сток).
Каждой дуге (i, j) приписана некоторая
пропускная способность с(i,j) 0 (без
потери общности считаем её
целочисленной величиной),
определяющая максимальное значение
потока, который может протекать по
данной дуге.

Потоком
в
сети
называют
целочисленную функцию f(i, j), заданную
на множестве дуг E и обладающей
следующими свойствами:
1. Ограничение потока пропускной
способностью
Для любой дуги (i, j) E выполняется
неравенство f(i, j) c(i, j).

2. Сохранение потока
Для любой вершины q V,
выполняется равенство
q s
и
q t
f (i, q) f (q, j)
i V
(i , q) E
j V
(q , j) E
Т. е. сумма потока, заходящего в q, равна
сумме потока, выходящего из q (поток без
потерь и накоплений)

Требуется определить значение
максимального потока, который
можно пропустить от источника s к
стоку t, и его распределение по дугам.

Пример
У компании Lycky Puck в Ванкувере есть фабрика
(источник s), производящая хоккейные шайбы, а в
Виннипеге – склад (сток t), где эти шайбы хранятся.
Компания арендует места на грузовиках других фирм
для доставки шайб с фабрики на склад. Поскольку
грузовики ездят по определенным маршрутам (ребрам)
между городами (вершинами) и имеют ограниченную
грузоподъемность, компания Lycky Puck может
перевозить не более c(u,v) ящиков в день между каждой
парой городов u и v. Компания Lycky Puck не может
повлиять на маршруты и пропускную способность. Ее
задача – определить, какое наибольшее количество
ящиков в день можно отгружать, и затем производить
именно такое количество, поскольку не имеет смысла
производить шайб больше, чем можно отправить на
склад.

Методы решения задачи
Линейное программирование
Представить задачу о максимальном потоке как задачу
линейного программирования. Переменными являются
потоки по рёбрам, а ограничениями - сохранение потока
и ограничение пропускной способности.
Алгоритм Форда-Фалкерсона
Найти любой увеличивающий путь. Увеличить поток по
всем его рёбрам на минимальную из их остаточных
пропускных способностей. Повторять, пока
увеличивающий путь есть. Алгоритм работает только
для целых пропускных способностей.

10.

Пример 1
Дадим формулировку задачи о максимальном
потоке в терминах линейного программирования.
Пусть ХKM - объем перевозок из пункта К в пункт М.
К = 0,1,2,3, М = 1,2,3,4, причем перевозки возможны
лишь в пункт с большим номером. Значит, всего
имеется 9 переменных ХKM, а именно, Х01 , Х02 , Х03 , Х12
, Х13 , Х14 , Х23 , Х24 , Х34 .
s=0
t=4

11.

Задача линейного программирования,
нацеленная на максимизацию потока, имеет вид:
F → max ,
Х01 +Х02 +Х03 =F
-Х01 +Х12 +Х13 +Х14 = 0
-Х02 -Х12 +Х23 +Х24 = 0
-Х03 -Х13 -Х23 +Х34 = 0
-Х14 -Х24 -Х34 = - F
Х01 ≤ 2
Х02 ≤ 3
Х03 ≤ 1
Х12 ≤ 4
Х13 ≤ 1
Х14 ≤ 3
Х23 ≤ 1
Х24 ≤ 2
Х34 ≤ 2
ХКМ ≥ 0 , К, М = 0, 1, 2, 3, 4
F≥0.

12.

Разрезом
называют множество дуг,
удаление которых из сети приводит к
«разрыву» всех путей, ведущих из s в t.
Пропускная способность разреза – это
суммарная пропускная способность дуг, его
составляющих.
!!! Найти разрезы в примере 1

13.

Теорема Л. Форда и Д. Фалкерсона:
Величина каждого потока из s в t не
превосходит
пропускной
способности
минимального разреза, разделяющего s и t,
причем поток, достигающий этого значения,
существует.
(Величина
максимального
потока
в
транспортной
сети
равна
величине
минимального разреза в ней)
!!! Найти минимальный разрез в примере 1

14.

С алгоритмической точки зрения эта
теорема малопродуктивна.
Генерация всех подмножеств дуг и
проверка,
является
ли
очередное
подмножество разрезом – «лобовое решение»,
приводит к высокой сложности алгоритма.
Кроме того, данный факт не помогает
найти способ распределения максимального
потока по дугам.

15.

Алгоритм Форда-Фалкерсона
«Техника меток» Л. Форда и Д. Фалкерсона
заключается в последовательном
(итерационном, поиском в ширину) построении
максимального потока путем поиска на каждом
шаге увеличивающей цепи, то есть пути, по
которому можно увеличить поток.
При этом узлы (вершины графа)
специальным образом помечаются. Отсюда и
возник термин «метка».

16.

Алгоритм Форда-Фалкерсона
Что представляет из себя метка
вершины?
первая цифра в метке – это номер
вершины, из которой идет поток в
данную вершину;
вторая цифра в метке – численное
значение потока, который можно
передать в данную вершину.

17.

Алгоритм Форда-Фалкерсона
На каждом шаге алгоритма вершины сети
могут находиться в одном из трех состояний:
вершина не имеет метки;
вершине присвоена метка, и она не
просмотрена, т. е. не все смежные с ней
вершины обработаны;
вершине присвоена метка, и она
просмотрена.

18.

Алгоритм Форда-Фалкерсона
Как только вершина-сток становится
помеченной, это говорит о том, что
очередная увеличивающая поток цепочка
найдена, итоговый суммарный поток
необходимо увеличить на величину потока
найденной цепочки, и перейти к
следующему шагу алгоритма.

19.

Алгоритм Форда-Фалкерсона
Дуга e=(u, v) сети является допустимой
дугой из u в v относительно потока f, если
e=(u, v) и f(e) прямые);
e=(v, u) и f(e)>0 (дуги второго типа,
обратные).
Второе условие говорит о том, что
допустимыми являются и дуги, входящие в
вершину u, по которым «уже пропущен
ненулевой поток».

Это пособие предназначено для студентов, изучающих курс дискретной математики и (или) теории графов. С его помощью Вы освоите тему "Максимальный поток и минимальный разрез в сети". Прямо из этого пособия Вы можете посчитать своё ИДЗ, даже если у Вас нет на компьютере MATLAB. Если же у Вас есть MATLAB, перейдите на эту страницу : там у Вас есть возможность вмешаться в сценарий (программу) вычислений. Здесь же задача о максимальном потоке в сети решается путём сведения к задаче линейного программирования.

Введём обозначения:

n =|V | − размер графа (количество вершин);
m =|E | − мощность графа (количество рёбер);
A − матрица инцидентности орграфа сети размером n ×m ; каждый её элемент a ik =1, если из i -й вершины выходит k -я дуга; a ik =−1, если в i -ю вершину входит k -я дуга; и a ik =0 в остальных случаях; в каждом столбце такой матрицы ровно одна единица, одна минус единица, а остальные нули;
s − номер вершины-источника сети; из этой вершины должны только выходить дуги, и любая другая вершина должна быть достижима из источника;
t − номер вершины-стока сети; в эту вершину должны только входить дуги, и из любой другой вершины должен быть достижим сток;
a s − s A ; в ней должны быть только единицы, т.к. из источника должны только выходить дуги;
a t − t -я строка матрицы инцидентности орграфа сети A ; в ней должны быть только минус единицы, т.к. в сток должны только входить дуги;
A st − матрица инцидентности орграфа сети A с выброшенными из неё s -й и t -й строками;
e − вектор-столбец длины m ; в каждом его элементе e k будет величина потока в k -й дуге;
c − вектор-столбец длины m ; в каждом его элементе c k ≥0 задаётся пропускная способность k -й дуги.

Тогда задача о максимальном потоке в сети может быть сформулирована как задача линейного программирования:

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

Задача, двойственная к задаче о максимальном потоке − это задача о минимальном разрезе. Для построения минимального разреза можно воспользоваться теоремами двойственности. Нужно:

удалить из орграфа сети все пустые (e k = 0) и насыщенные (e k = c k ) дуги;
найти компоненты связности оставшегося графа;
если таких компонент две, то выброшенные дуги дают минимальный разрез;
если появится больше двух компонент связности, то у орграфа сети есть несколько минимальных разрезов (соответствующая задача линейного программирования вырожденная).

Для вырожденной задачи на данной странице строится первый, ближайщий к источнику минимальный разрез.

Для правильной работы с этой страницей Ваш браузер должен поддерживать сценарии Java Script . Включите их.

Введите исходные данные в находящиеся ниже области ввода. В первой области нужно (точнее, можно) ввести координаты вершин для рисования орграфа сети. Они задаются в виде матрицы n ×2: в первом столбце − x -е координаты, во втором − y -е. Числа можно задавать целые, с десятичной точкой или в экспоненциальной форме. Числа разделяйте пробелами. Общее количество строк в этой области ввода определяет размер орграфа n − количество вершин. Эти исходные данные (координаты вершин) не являются обязательными: если их не задать, то орграф сети будет рисоваться в виде правильного n -угольника, а количество вершин будет определяться максимальным номером вершины в следующей области ввода.

В следующей области ввода левая часть − обязательная для заполнения. В ней определяется структура орграфа сети. Каждая дуга в орграфе соединяет две вершины. Номера этих вершин задаются в виде матрицы m ×2 в левой части второй области ввода. На каждой строке вначале задаётся 1-я вершина (хвост, источник) дуги, а затем через пробел 2-я (остриё, сток) дуги. В этих столбцах должны быть натуральные числа от 1 до n включительно. Числа разделяйте пробелами. В правой части задаются пропускные способности дуг − положительные действительные числа. Если этот столбец не задан, все пропускные способности считаются одинаковыми (единичными). Общее количество чисел в каждом из этих столбцов определяет мощность орграфа m − количество дуг.

Посчитать

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

Рассмотрим сеть распределения (рис. 4.21), в которой выделены пункты 0 (вход, например, склад готовой продукции производителя) и п (выход, распределительные центры, склады оптовых и розничных организаций, потребитель) и каждой дуге (отрезку), связывающей пункты i и j, сопоставлено число dij > 0, называемое пропускной способностью дуги. Величина пропускной способности характеризует максимальное допустимое количество материального потока, которое может проходить по соответствующей дуге в единицу времени.

Рис. 4.21.

Количество продукции, проходящее по дуге от i до j , будем называть потоком по дуге (i ,j ) и обозначать через . Очевидно, что

Если учесть, что весь материальный поток, вошедший в промежуточный пункт сети, должен полностью выйти из него, получим

Из естественного требования равенства потоков на входе и на выходе имеем

Величину Z назовем величиной потока в сети и поставим задачу максимизации Z при соблюдении обозначенных выше условий.

Поиск максимального потока сводится к поиску пропускной способности минимального разреза.

Рассмотрим универсальный алгоритм поиска в матричной форме.

Начальный этап алгоритма состоит в построении матрицы D 0, в которую заносятся значения пропускных способностей (для неориентированной дуги берем симметричные значения элементов матрицы ).

Основные шаги алгоритма состоят в поиске некоторого пути и коррекции потока на этом пути.

При поиске пути используем процесс отмечаний. Метим символом * нулевые строку и столбец матрицы (вход сети). В 0-й строке отыскиваем , метим соответствующие столбцы индексами

и переносим метки столбцов на строки. Затем берем ί-ю отмеченную строку, ищем в ней непомеченный столбец с , которому сопоставляем метки-индексы

Метки столбцов переносим на строки, и этот процесс продолжаем до тех пор, пока не будет отмечен п-й столбец.

Затем "обратным ходом" по индексам выясняем путь, приведший к η-й вершине, уменьшаем пропускные способности дуг пути (элементы матрицы) на V n и увеличиваем симметричные элементы на эту же величину.

Такая процедура продолжается до тех пор, пока отмечание n -й вершины не станет невозможным.

Максимальный поток может быть найден вычитанием из исходной матрицы D 0, получаемой после приведенной выше корректуры матрицы пропускных способностей:

Пример 4.4

Производство размещено в Москве. Для распределения продукции предприятие привлекает посредников, которые работают с предприятием через распределительные центры различных уровней. В европейской части России работает оптовое предприятие 1, обслуживаемое центральным распределительным центром. Оптовое предприятие 2 работает в ближайшем зарубежье (Украина, Белоруссия) и обслуживается региональным распределительным центром. Есть у предприятия на местном рынке (Москва и Московская область) свои клиенты – ритейлеры, которые получают продукцию с городского распределительного центра. Запасы регионального и городского распределительных центров пополняются с центрального распределительного центра.

Выделим фрагмент распределительной сети:

склад готовой продукции производственного предприятия;
центральный распределительный центр;
региональный распределительный центр;
городской распределительный центр;
два оптовых предприятия;
розничная точка, принадлежащая компании;
потребители.

Рис. 4.22.

Каждое звено сети распределения обозначим цифрой, а над дугами проставим пропускную способность. Пропускная способность в зависимости от вида звена может быть выражена через объем производственной мощности, плановую потребность (спрос) потребителей и емкость рынка.

Граф сети распределения продукции представлен на рис. 4.23. Построим матрицу D 0, в которую занесем значения пропускных способностей звеньев распределительной сети (рис. 4.24).

Рис. 4.23.

Рис. 4.24.

Из нулевой строки отметим вершины (строки-столбцы) 1, 2 и 3 индексами μ = 0 и V, равными 30,10 и 10.

Из помеченной строки 1 отметим вершины 4 и 5 индексами μ = 1 и V4 = min (30,15) = 15, V5 = min (30,10) = 10.

Из строки 3 отметим вершину 6 и, наконец, из строки 4 – вершину 7 (рис. 4.25).

Рис. 4.25.

Обратным ходом по μ обнаруживаем путь: к вершине 7 от 4, к вершине 4 от 1, к вершине 1 от 0; корректируем элементы D 0 на величину потока V7 = 15.

Очередной шаг дает путь с потоком 5 (рис. 4.26).

Рис. 4.26.

Последующий шаг дает результат, представленный на рис. 4.27.

Рис. 4.27.

Дальнейшее отмечание невозможно. Отсюда получаем матрицу максимального потока (рис. 4.28).

Рис. 4.28.

В результате применения алгоритма нахождения максимального потока в сети получены результаты, представленные на рис. 4.29. Пары цифр в скобках, показанные на дугах графа, означают максимальную пропускную способность дуги и рекомендуемый объем поставки товаров в сеть.

Решить задачу нахождения максимального потока в транспортной сети с помощью алгоритма Форда-Фалкерсона, и построить разрез сети S.
Исходные данные:
Дана сеть S(X,U)
- исток сети; - сток сети, где ∈X; ∈X.
Значения пропускных способностей дуг заданы по направлению ориентации дуг: от индекса i к индексу j.

r = 39; r = 44; r = 33; r = 53; r = 10;
r = 18; r = 95; r = 16; r = 23; r = 61;
r = 81; r = 71; r = 25; r = 15; r = 20

1. Зададим на сети нулевой поток (на всех дугах величина потока равна 0). Нулевой поток - это начальный допустимый поток на сети. Значение потока на каждой дуге будем указывать за скобками пропускной способности дуги.). Значение потока, равное «0», не указываем.
2. Выбираем на сети (произвольно) путь, ведущий из вершины x0 в вершину x7:
X0-X1-X4-X6-X7
3. Находим и увеличиваем поток на эту величину. Ребро Х1-Х4 помечаем как рассмотренное.

4. Выбираем еще один путь, например: Х0-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х0-Х2 помечаем как рассмотренное.

5. Выбираем еще один путь, например: Х0-Х3-Х2-Х5-Х7, находим и увеличиваем поток на эту величину. Ребро Х3-Х2 помечаем как рассмотренное.

6. Более путей от Х0 до Х7 нет, суммируем увеличения потока: 25+10+20=55.
Вывод: максимальный поток равен 55.

2) Построить разрез сети S.
Процедура «пометок вершин».
Начальное состояние: все вершины не имеют пометок.
Вершине Х0 приписывается пометка. Всем вершинам , для которых дуга не насыщена присваиваются пометки (красные круги)

Определяем дуги минимального разреза: это дуги, начала которых находятся в помеченных вершинах, а концы - в непомеченных вершинах.
Это дуги:
Таким образом, минимальный разрез данной сети
Вычисление величины максимального потока