Добавим фиктивные исток и сток. От истока ко всем белым вершинам проведем ребра, весом в B (цена перекраски в черный). От черных вершин ко стоку проведем ребра, весом в W (цена перекраски в белый). И между всеми соседними вершинами (будь они одного или разных цветов) - ставим ребро весом в G (серая линия). Величина максимального потока будет ответом на задачу.
Источник: Всеукраинская школьная олимпиада по информатике, 2007, День 1
Решение
Все, что нам надо - это разделить каждую вершину на две, и между ними поставить ребро, весом в ограничение пропускной способности данной вершиныРешение
В классической задаче о минимальном разрезе удалять нужно ребра. Не проблема! Разобьем вершины на 2, и поставим между ними ребро, весом в 1. Тогда ответ к задаче - нахождение минимального разреза в графе (что и есть максимальным потоком).Источник: Харьковская зимняя школа по программированию, 2009, День 3
После перехода по автомату из i в j по ребру k, стираются все переходы из i по ребру k, а также все переходы в j по ребру k. Требуется вывести количество путей из A в B по такому автомату.
Решение
Задача сводится к нахождению максимального количества путей, причем из одной вершины не выходят более одного ребра одного цвета. Сведем задачу к нахождения максимального потока. Для каждой вершин создадим k+1 вершину в перестроенной сети. Первая вершина будет входом, остальные вершины будут представлять цвета. Из вершины входа проведем по ребру пропускной способностью 1 в каждую из k вершин, соответствующих цвету. Из вершины соответствующих цвету i проведем все ребра цвета i во входы концов ребер. Найдя максимальный поток в такой сети, получим максимальное количество путей удовлетворяющих требуемому свойству.Решение
Построим сеть. Создадим для каждого типа монет по одной вершине. Эти вершины будут соответствовать Вашим монетам. Нужно собрать как можно больше уникальных монет, поэтому проведем ребро пропускной способности 1 в сток из каждой такой вершины. В вершины, соответствующие монетам, которые у Вас есть изначально, проведем ребро, пропускная способность которого равна количеству таких монет у Вас.Для каждого члена клуба (кроме 1, тоесть Вас) заведем по одной вершине. Эта вершина может принимать не более одной монеты, которой у него нет и отдавать
не более k-1 монеты, которых у него k (k > 1). Естественно, член клуба отдает одну монету взамен одной полученной.
Таким образом, в каждую такую вершину нужно провести ребро пропускной способности 1 из вершин соответствующих монетам, которых нет у этого члена клуба. А из этих вершин нужно провести ребра пропускной способностью k i - 1 в вершину i, соответствующую монетам, которых у члена клуба больше одной.
Построенная сеть отражает процессы обмена в клубе. Максимальный поток в такой сети будет равен максимальному количеству монет, которые могуть быть собраны Вами.
Источник: Харьковская зимняя школа по программированию, 2009, День 4
Дано описание системы охлаждения. Нужно выяснить, каким образом можно пустить жидкость по трубам, чтобы выполнялись все указанные условия.
Решение
Это задача на нахождение циркуляции в сети с заданными нижними ограничениями на ребра. Если по ребру (u, v) должен проходить поток в отрезке , то в перестроенной сети будет три ребра (откуда, куда, вес): (u, v, r - l), (S, v, l), (u, T, l). S, T - дополнительно введенные сток и исток соответственно. Фактически мы пропускаем по ребру необходимый минимальный поток, после чего балансируем его так, чтобы получить циркуляцию.При обмене информацией между абонентами вычислительной сети, при параллельных вычислениях на многомашинном комплексе, когда решение задачи распределено между несколькими процессорами, при использовании в вычислительной сети общей памяти, когда каждый процессор получает ограниченный доступ к общим модулям памяти, возникает задача передачи максимального объема информации в заданный отрезок времени.
При работе транспортной системы, когда осуществляется обмен транспортными единицами между узлами сети возникает задача передачи максимального числа транспортных единиц в заданный отрезок времени.
При передаче энергии в электрических сетях, жидкости в трубопроводных системах возникает задача распределения и передачи максимального объема энергии или вещества в заданный отрезок времени.
Особенностью сети является наличие вершины-истока и вершины-стока, ориентация всех отрезков линий в графе и отсутствие петель и кратных дуг.
Объем информации, энергии или вещества, передаваемый в сети от узла 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 .
Алгоритм расчета максимального потока в сетях
ШАГ 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. Сетевой график выполнения проекта
При планировании рационального распределения продукции в сети распределения необходимо согласовывать пропускную способность каналов с потребностями клиентов и с мощностью производственного предприятия. Данный класс задач решается методом нахождения максимального потока.
Рассмотрим сеть распределения (рис. 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. Пары цифр в скобках, показанные на дугах графа, означают максимальную пропускную способность дуги и рекомендуемый объем поставки товаров в сеть.
Сумма потоков через дуги, инцидентные v , равна сумме потоков через дуги, инцидентные w ; эта сумма называется величиной потока. Будем в первую очередь интересоваться потоками, имеющими наибольшую возможную величину, - так называемыми максимальными потоками. В общем случае сеть может иметь несколько различных максимальных потоков, однако их величины должны совпадать. (4)
Изучение максимальных потоков через сеть N = (V,D,a) тесно связано с понятием разреза, т.е. такого множества A дуг орграфа D, которое обладает тем свойством, что любая простая цепь из v в проходит через дугу, принадлежащую A. Пропускной способностью разреза называется сумма пропускных способностей принадлежащих ему дуг. Разрезы, обладающие наименьшей возможной пропускной способностью, называются минимальными разрезами.
Величина любого потока не превышает пропускной способности любого разреза, и, следовательно, величина любого максимального потока не превышает пропускной способности любого минимального разреза. Однако сразу не ясно, что два последних числа всегда равны между собой; Этот результат был получен американскими математиками Фордом и Фалкерсоном в 1955 году и назван теоремой о максимальном потоке и минимальном разрезе.
Теорема (о максимальном потоке и минимальном разрезе) . Во всякой сети величина любого максимального потока равна пропускной способности любого минимального разреза.
Теорема о максимальном потоке и минимальном разрезе позволяет проверять, максимален данный поток или нет, но только для достаточно простых сетей. Разумеется, на практике приходится иметь дело с большими и сложными сетями, и в общем случае трудно найти максимальный поток простым подбором. Опишем один алгоритм нахождения максимального потока в любой сети с целочисленными пропускными способностями.
Шаг 1 . Сначала подберем поток, обладающий ненулевой величиной (если такой поток существует). Например, если N – сеть, представленная на рис. 29.3, то подходящим будет поток, изображенный на рис. 29.4. Стоит отметить, что чем больше величина выбранного нами начального потока , тем проще будут последующие шаги.
Шаг 2 . Исходя из N, строим новую сеть N’ путем изменения направления потока на противоположное. Более точно, любая дуга a, для которой(a) = 0, остается в N’ со своей первоначальной пропускной способностью, а любая дуга a, для которой , заменяется дугой a с пропускной способностью и противоположно направленной дугой с пропускной способностью (a). Сеть N’ в нашем примере показана на рис. 29.5. Вершина v уже не является источником,а – стоком.
Шаг 3 . Если в сети N’ мы сможем найти ненулевой поток из v в, то его можно добавить к первоначальному потокуи получить в N новый поток’большей величины. Теперь можно повторить шаг 2, используя при построении сети N’ новый поток’ вместо. Повторяя эту процедуру, мы в конце концов придем к сети N’ , не содержащей ненулевых потоков; тогда соответствующий потокбудет максимальным потоком. Например, на рис. 29.5 существует ненулевой поток, в котором потоки через дуги (v,u ), (u,z ), (z,x ), (x,y ) и (y, ) равны единице, а потоки через остальные дуги равны нулю. Добавляя этот поток к потоку на рис. 29.4, получим поток, изображенный на рис. 29.6; повторяя шаг 2, легко показать, что это и есть максимальный поток.
Используемая литература:
(1) http://pgap.chat.ru/zap/zap264.htm#0
(2) Асанов М.О., Баранский В.А., Расин В.В. Дискретная математика: графы матроиды, алгоритмы
(3) Басакер Р., Саати Т. Конечные графы и сети.
(4) Уилсон Р. Введение в теорию графов