Пусть задан ориентированный граф G=, в котором направление каждой дуги vÎV означает направление движения потока (например поток автомобилей), пропускная способность каждой дуги равна d(v). На множестве вершин E выделены две вершины t и s . Вершина t является источником потока, s - стоком. Требуется определить максимальный поток, который может быть пропущен из вершины t в s .

Обозначим через x(v) величину потока, движущегося по дуге v . Очевидно, что

0£ x(v) £ d(v) , vÎV . (6. 1)

В каждой вершине iÎE\{t,s} объем потока входящего равен объему потока выходящего, т.е. справедливо равенство

{x(v )|i Î V + (i)}= {x(v)| iÎ V - (i)}

{x(v)| iÎV + (i)} - {x(v)| iÎV - (i)}=0. (6.2)

Для вершины t

{x(v)| iÎV + (i)} -{x(v)¦ iÎV - (i)}=-Q, (6.3)

для вершины s

{x(v)| iÎ V + (i)} -{x(v)¦ i Î V - (i)}= Q. (6.4)

Величина Q является величиной потока, который выходит из вершины t и входит в вершину s .

Требуется определить

Q ® max (6.5)

при ограничениях (6.1-6.4).

Величины Q, x(v) , vÎV, удовлетворяющие ограничениям (6.1-6.4) будем называть потоком в сети, и если они максимизируют величину Q , то максимальным потоком. Нетрудно видеть, что значения Q=0, x(v)=0, vÎV , являются потоком в сети.

Задача (6.1-6.5) является задачей линейного программирования и ее можно решить алгоритмами симплекс-метода.

Разобьем множество вершины Е на две непересекающиеся части Е1 и Е2 таким образом, чтобы tÎE1, sÎE2 . Разрезом V(E1,E2) , разделяющим t и s будем называть множество V(E1,E2)ÌV такое, что для каждой дуги v Î V(E1,E2) либо h1(v)ÎE1 и h2(v)ÎE2 , либо h1(v)ÎE2 и h2(v)ÎE1 .

Разобьем множество V(E1,E2) на две части V(E1,E2,+),V(E1,E2,-) следующим образом:

V(E1,E2,+)={vÎV(E1,E2)| h1(v)ÎE1 и h2(v)ÎE2}

V(E1,E2,-)= { vÎV(E1,E2)| h2(v)ÎE1 и h1(v)ÎE2}

Пропускной способностью разреза будем называть

Q(E1,E2) = {x(v)| vÎV(E1,E2,+)}-{x(v)| vÎV(E1,E2,-)}

Справедлива следующая

Теорема 1 . (О максимальном потоке и минимальном разрезе).

В любой сети величина максимального потока из источника t в сток s равна минимальной пропускной способности Q(E1,E2) среди всех разрезов V(E1,E2) , разделяющих вершины t и s .

Заметим, что в максимальном потоке

x(v)=d(v) , vÎV(E1,E2,+),

x(v)=0 , vÎV(E1,E2,-).

Пусть Q, x(v), vÎV, - некоторый поток в сети, последовательность

t=i(0),v(1),i(1),v(2),i(2),...,v(k),i(k)=s,

является цепью, соединяющих вершины t и s . Зададим на этой цепи направление движения от вершины t к s . Дуга v(j) из этой цепи называется прямой, если ее направление совпадает с направлением движения от t к s , и обратной в противном случае. Эту цепь будем называть путем увеличения потока , если для прямых дуг v цепи x(v) < d(v) и для обратных x(v) > 0 . По этой цепи можно пропустить дополнительный поток q из t к s величиной q = min (q1,q2), где q1=min (d(v) -x(v)) , минимум берется по всем прямым дугам цепи, q1=min (x(v)) , минимум берется по всем обратным дугам цепи.

Теорема 2 .

Поток Q, x(v) , vÎV , максимальный тогда и только тогда, когда не существует пути увеличения потока.

Предлагаемый алгоритм решения задачи о максимальном потоке в сети, основан на поиске пути увеличения потока из t в s , который в свою очередь основан на процессе расстановки пометок вершин. Будем говорить, что

вершина i помечена пометкой q(i)>0 , а также известна дуга прямая дуга v(i) , через которую поступил этот поток, либо помечена пометкой , если до нее дошел некоторый дополнительный поток величиной q(i)>0 , а также известна обратная дуга v(i) , через которую поступил этот поток;

вершина i просмотрена, если помечены все соседние с ней вершины.

Если помечена вершина s, то найден путь увеличения потока величиной q , который пропускается по этому пути. Для описания алгоритма нам понадобится также массив SPW , в который помещаются номера помеченных вершин в порядке их пометки. С1 - номер в массиве SPW просматриваемой вершины, С2 - номер последней помеченной вершины в этом массиве.

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

Рассмотрим ребро (i, j) с (начальной) пропускной способностью. В процессе выполнения алгоритма части этих пропускных способностей «забираются» потоками, проходящими через данное ребро, в результате каждое ребро будет иметь остаточную пропускную способность. Запись - остаточная пропускная способность. Сеть в которой все ребра имеют остаточную пропускную способность, назовем остаточной.

Для произвольного узла j, получающего поток из узла i, определим метку, где - величина потока, протекающего от j узла к узлу i. Чтобы найти максимальный поток, выполняем следующие действия.

Для всех ребер положим остаточную пропускную способность равной первоначальной пропускной способности, т.е. приравняем =. Назначим и пометим узел 1 меткой. Полагаем i=1.

Множество узлов j, в которые можно перейти из узла I по ребру с положительной остаточной пропускной способностью >0 для всех j. Если, выполняем 3 этап, в противном случае переходим к 4.

В находим узел k, такой, что. Положим и пометим узел k меткой. Если k=n, сквозной путь найден, и переходим к 5 этапу, в противном случае полагаем i=k и возвращаемся к 2 этапу.

Откат назад. Если i=1, сквозной путь не возможен, и переходим к 6. Если, находим помеченный узел r, непосредственно предшествующий узлу i, и удаляем его из множества узлов, смежных с узлом r. Полагаем i=r и возвращаемся ко 2 этапу.

Определение остаточной сети. Обозначим через множество узлов, через которые проходит p_й найденный сквозной путь от узла источника (узел 1) до узла стока (узел n).тогда максимальный поток, проходящий по этому пути

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

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

1) , если поток идет от узла i к j,

2) , если поток идет от узла j к i.

а) при m найденных сквозных путях максимальный поток выражается

б) Имея значения начальных и конечных пропускных способностей ребра (i, j), можно вычислить оптимальный поток через это ребро следующим образом. Положим. Если >0, поток, проходящий через ребро (i, j) равен. Если >0, тогда поток равен. (случай, когда одновременно >0 и >0, невозможен).

Пример 1. Найти максимальный поток в сети рис. 1

Итерация 1. =

3) k=3, так как. Назначаем и помечаем узел 3 меткой. i=3 и возвращаемся к 2)

5) k=5 и. Помечаем узел 5 меткой. Получаем сквозной путь.

6) сквозной путь определяем по меткам, начиная с узла 5 и заканчивая узлом 1: . и. Вычисляем остаточные пропускные способности вдоль пути:

Итерация 2.

1) и помечаем узел 1 меткой. i=1

2») (, поэтому узел 5 не включается в

3») k=4, и помечаем узел 4 меткой. i=4 и возвращаемся к 2)

2""") (так как узлы 1 и 3 помечены, они не включаются в)

3""") k=5 и. Помечаем узел 5 меткой. Получен сквозной путь. Переходим к 5)

Итерация 3.

1) и помечаем узел 1 меткой. i=1

3) k=2, и помечаем узел 2 меткой. i=2 и возвращаемся к 2)

3") k=3 и. Помечаем узел 3 меткой. i=3 и возвращаемся к 2)

2») (так как) переходим к 4)

4) метка узла 3 показывает номер предшествующего узла. На этой итерации узел 3 в дальнейшем во внимание не принимается, его метку вычеркиваем. и возвращаемся к 2)

2""") (так как узел 3 удален из возможного сквозного пути)

3""") и. Помечаем узел 5 меткой. Получен сквозной путь. Переходим к 5)

5) и. Вычисляем остаточные пропускные способности вдоль пути:

Итерация 4. на этой итерации получен путь с

Итерация 5. на этой итерации получен путь с

Итерация 6. новые сквозные пути невозможны, поскольку все ребра, исходящие из узла 1, имеют нулевые остаточные пропускные способности. Переходим к 6) для определения решения

6) максимальный объем потока в сети равен единиц.

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

Результаты вычислений: табл. 1

		Величина потока	направление
	(20,0) - (0,20)=(20, - 20)
	(30,0) - (0,30)=(30, - 30)
	(10,0) - (0,10)=(10, - 10)
	(40,0) - (40,0)=(0,0)
	(30,0) - (10,20)=(20, - 20)
	(10,5) - (0,15)=(10, - 10)
	(20,0) - (0,20)=(20, - 20)
	(20,0) - (0,20)=(20, - 20)

Графическое последовательное выполнение алгоритма нахождения максимального потока (пример 1)

д) е) Сквозных путей нет

Рис.

Исходные данные о транспортной системе, например, внутризаводской, приведенные на рис. 2, можно также задать таблицей (табл. 2).

Табл.2. Исходные данные к задаче о максимальном потоке

Очевидно, максимальная пропускная способность транспортной системы не превышает 6, поскольку не более 6 единиц грузов можно направить из начального пункта 0, а именно, 2 единицы в пункт 1, 3 единицы в пункт 2 и 1 единицу в пункт 3. Далее надо добиться, чтобы все 6 вышедших из пункта 0 единиц груза достигли конечного пункта 4. Очевидно, 2 единицы груза, пришедшие в пункт 1, можно непосредственно направить в пункт 4. Пришедшие в пункт 2 грузы придется разделить: 2 единицы сразу направить в пункт 4, а 1 единицу - в промежуточный пункт 3 (из-за ограниченной пропускной способности участка между пунктами 2 и 4). В пункт 3 доставлены такие грузы: 1 единица из пункта 0 и 1 единица из пункта 3. Их направляем в пункт 4. Итак, максимальная пропускная способность рассматриваемой транспортной системы - 6 единиц груза. При этом не используются внутренние участки (ветки) между пунктами 1 и 2, а также между пунктами 1 и 3. Не догружена ветка между пунктами 1 и 4 - по ней направлены 2 единицы груза при пропускной способности в 3 единицы. Решение можно представить в виде таблицы (табл. 3)

Табл.3. Решение задачи о максимальном потоке

Пункт отправления	Пункт назначения	План перевозок	Пропускная способность

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

Х 01 + Х 02 + Х 03 = F (0)

Х 01 + Х 12 + Х 13 + Х 14 = 0 (1)

Х 02 - Х 12 + Х 23 + Х 24 = 0 (2)

Х 03 - Х 13 - Х 23 + Х 34 = 0 (3)

Х 14 - Х 24 - Х 34 = - F (4)

Х КМ? 0, К, М = 0, 1, 2, 3, 4

Здесь F - целевая функция, условие (0) описывает вхождение грузов в транспортную систему. Условия (1) - (3) задают балансовые соотношения для узлов 1- 3 системы. Другими словами, для каждого из внутренних узлов входящий поток грузов равен выходящему потоку, грузы не скапливаются внутри и системы и не «рождаются» в ней. Условие (4) - это условие «выхода» грузов из системы. Вместе с условием (0) оно составляет балансовое соотношение для системы в целом («вход» равен «выходу»). Следующие девять неравенств задают ограничения на пропускную способность отдельных «веток» транспортной системы. Затем указана неотрицательность объемов перевозок и целевой функции. Ясно, что последнее неравенство вытекает из вида целевой функции (соотношения (0) или (4)) и неотрицательности объемов перевозок. Однако последнее неравенство несет некоторую общую информацию - через систему может быть пропущен либо положительный объем грузов, либо нулевой (например, если внутри системы происходит движение по кругу), но не отрицательный (он не имеет экономического смысла, но формальная математическая модель об этом «не знает»).

Алгоритм расчета максимального потока в сетях

ШАГ 1. Начальные присваивания. Текущему значению А т максимального потока в сети присваиваем значение 0. ШАГ 2. Выбор независимых маршрутов в сети и определение потоков в них. Из всего множества возможных маршрутов в сети от источника к стоку выбираем независимые маршруты М 1 , … , М k , не имеющие общих вершин, кроме начальной (источника v и ) и конечной (стока v с ). Для каждого выбранного маршрута М i (1£ i £ k ) определяем максимальный поток А (М i ).ШАГ 3. Коррекция текущего значения максимального потока в сети. Прибавляем найденные на ШАГе 2 значения максимальных потоков в независимых маршрутах М 1 , … , М k к текущему общему максимальному потоку в сети: А т := А т + А (М 1)+ А (М 2)+…+ А (М k ).ШАГ 4. Коррекция сети. Найденные на ШАГе 2 максимальные потоки А (М 1), … , А (М k )вычитаем из пропускной способности соответствующих дуг сети. Дуги с нулевой остаточной пропускной способностью удаляем.ШАГ 5. Проверка завершения работы алгоритма. Если после коррекции в сети не осталось маршрутов из источника v и в сток v с , то искомый максимальный поток в сети равен найденному текущему А := А т , алгоритм завершает свою работу, поскольку все пропускные возможности сети исчерпаны. Если же в корректированной сети существуют маршруты из источника v и в сток v с , то переход на ШАГ 2 и продолжение выполнения алгоритма. Пример 2. Найти максимальный поток в сети на рис.1.15 по данному алгоритму. Решение.ШАГ 1. Начальные присваивания. А т : = 0.

I итерация. ШАГ 2. Выбор независимых маршрутов в сети и определение потоков в них. В качестве М 1 возьмем маршрут(v и =V 1 , V 2 , V 5 , v с =V 7), рассмотренный в примере 1. Для него А (М 1) = 10.

Также несложно выделить независимый от М 1 маршрут М 2 = (v и =V 1 , V 3 , V 6 , v с =V 7). Выполним для него расчет максимальной пропускной способности и скорректируем пропускную способность дуг: А (М 2)= min {d 13 , d 36 , d 67 }= min {45, 40, 30}= 30. d 13 ¢= d 13 - 30 = 15, d 36 ¢= d 36 - 30 = 10, d 67 ¢= d 67 - 30 = 0.

ШАГ 3. Коррекция текущего значения максимального потока в сети. А т := А т + А (М 1)+ А (М 2) = 0 + 10+ 30 = 40.ШАГ 4. Коррекция сети. Найденные на ШАГе 2 максимальные потоки А (М 1), А (М 2) в маршрутах М 1 , М 2 вычитаем из пропускной способности их дуг. Дуги с нулевой остаточной пропускной способностью удаляем. Результат дан на рис.1.16 а. а) б)Рис.1.16. Результат коррекции сети после итераций I и IIШАГ 5. Проверка завершения работы алгоритма. В корректированной сети (рис.1.16 а) существуют маршруты из источника v и в сток v с , например М 3 = (v и =V 1 , V 4 , V 2 , V 5 , v с =V 7). Продолжение выполнения алгоритма.

II итерация. ШАГ 2. В качестве единственного независимого маршрута примем М 3 = (v и =V 1 , V 4 , V 2 , V 5 , v с =V 7). Для него:

А (М 3)= min {d 14 , d 42 , d 25 , d 57 }= min {15, 10, 10, 15}= 10.

d 14 ¢= d 14 - 10 = 5, d 42 ¢= d 42 - 10 = 0, d 25 ¢= d 25 - 10 = 0, d 57 ¢= d 57 - 10 = 5.

ШАГ 3. А т := А т + А (М 3) = 40 + 10= 50.

ШАГ 4. Коррекция сети. Максимальный поток А (М 3)вычитаем из дуг маршрута М 13 . Результат дан на рис.1.16 б.

ШАГ 5. В корректированной сети не осталось маршрутов из источникав сток. А := А т := 50, завершение работы алгоритма.Ответ: максимальный поток в сети на рис.1.15 равен 50.

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

Сетевое планирование

Любую задачу по проектированию либо построению достаточно сложного объекта (проект ) можно разбить на ряд более мелких составляющих шагов. От правильного выбора последовательности выполнения данных шагов зависят сроки выполнения всего проекта.

Весь комплекс действий по выполнению проекта представляют в виде совокупности событий и работ . Событиями называют отдельные этапы проекта. Работами называют процесс их выполнения. Весь комплекс событий и работ, необходимых для выполнения проекта, может быть представлен в виде двухполюсной сети Г = ({v и, v з }, V, X ), в которой:

а) все события обозначены множеством вершин V, среди них выделено исходное событие v и (начало работ) и завершающее событие v з (завершение выполнения всего проекта), внутренние вершины сети задают промежуточные события - этапы, которые необходимо выполнить в процессе реализации проекта,

б) все работы обозначены дугами, соединяющими между собой пары событий - вершин.

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

В качестве примера рассмотрим организацию некоторого производства. Проект требует выполнения следующих работ:

I) маркетинговые исследования, II) предпроектные исследования по оборудованию, III) организация сети сбыта, IV) проведение рекламной кампании, V) разработка технического задания на производственное оборудование, VI) разработка технической документации на производственные помещения и коммуникации, VII) закупка стандартного оборудования, VIII) проектирование и изготовление нестандартного оборудования, IX)строительство производственных помещений и монтаж коммуникаций, X) монтаж стандартного оборудования, XI) монтаж нестандартного оборудования, XII) пусконаладочные работы.

Данные работы обозначим в сетевом графике дугами с соответствующими номерами.

Событиями в данном проекте будут следующие:

1) начало работ (исходное событие), 2) завершение маркетинговых исследований, 3) завершение предпроектных исследований, 4) организация сети сбыта, 5) организация рекламной кампании, 6) подготовка технического задания на производственное оборудование, 7) завершение разработки технической документации на производственные помещения и коммуникации, 8) завершение закупки стандартного оборудования, 9) завершение проектирования и изготовления нестандартного оборудования, 10) завершение строительства производственных помещений и монтажа коммуникаций, 11) завершение установки оборудования и пуско-наладочных работ,

12) завершение проекта (завершающее событие).

Событиям сопоставляем вершины с соответствующими номерами. Сетевой график выполнения проекта дан на рис. 1.17:

Рис.1.17. Сетевой график выполнения проекта

Это пособие предназначено для студентов, изучающих курс дискретной математики и (или) теории графов. С его помощью Вы освоите тему "Максимальный поток и минимальный разрез в сети". Прямо из этого пособия Вы можете посчитать своё ИДЗ, даже если у Вас нет на компьютере 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 − количество дуг.

Посчитать

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

Математик Джордж Бернард Данциг, с 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, по которым «уже пропущен
ненулевой поток».