Методические указания к выполнению расчетных работ по теории графов и сетей, страница 12

9.3Выделяем в D  простую цепь 2  v1v3v5 из v1 в v5 . Увеличиваем поток  (x) покаждой дуге x из  2 на одинаковую величину a2  7 до насыщения дуги (v3 , v5 ), приэтом поток по дуге (v1 , v3 ) не превышает ее пропускной способности. В результате поток1 меняется на поток  2 , а из орграфа D  удаляется дуга (v3 , v5 ). На рис. 9.4 приведеныизображения орграфа D с потоком  2 , а также соответствующего этому потоку вспомогательного орграфа D.D2Рис. 9.4Выделяем в D  простую цепь 3  v1v3v4v5 из v1 в v5 . Увеличиваем поток  (x) покаждой дуге x из  3 на одинаковую величину a3  3 до насыщения дуги (v4 , v5 ), приэтом потоки по дугам (v1 , v3 ) , (v3 , v4 ) не превышают их пропускных способностей.

В результате поток  2 меняется на поток  3 , а из орграфа D  удаляется дуга (v4 , v5 ) . На рис.9.5 приведены изображения орграфа D с потоком  3 , а также соответствующего этомупотоку вспомогательного орграфа D.D3Рис. 9.5Мы видим, что для орграфа D, соответствующего потоку  3 , не существует путииз источника в сток, а следовательно,  3 – полный поток.55Как мы увидим далее, полученный полный поток  3 не является максимальным.Для того чтобы иметь возможность увеличивать полный поток до максимального нам понадобится новое понятие.Орграф приращений.

Введем для транспортной сети D  (V , X ) и потока  в~этой сети орграф приращений I ( D, )  (V , X ). Для любой дуги x  (v, w)  X обозначим~~x  (w, v). Для каждой дуги x  X выполняется: (а) x  X   ( x)  c( x); (б) x  X   ( x)  0.Замечание 9.1. В дальнейшем мы будем искать в орграфе приращений простые цепи из v1 в vn . Поэтому в нем можно не учитывать дуги, заходящие в v1 , а также исходящие из vn .

Будем орграф приращений без указанных дуг называть модифицированным.Разбор типового варианта (продолжение). (б) Построить орграф приращенийI ( D,3 ).Решение. На рис. 9.6 приведено изображение орграфа I ( D,3 ), а на рис. 9.7 – изображение модифицированного орграфа I ( D,3 ).Рис. 9.6Рис. 9.7Для дальнейшего понадобитсяТеорема 9.1 (Форда – Фалкерсона). Поток  в транспортной сети D являетсямаксимальным тогда и только тогда, когда в орграфе приращений I ( D,  ) вершина v n(сток транспортной сети D ) не достижима из v1 (источника транспортной сети D ).Используя теорему Форда – Фалкерсона, нетрудно описать алгоритм построениямаксимального потока в транспортной сети D.Алгоритм 9.2 (Форда – Фалкерсона)Шаг 1. Пусть  – любой поток в транспортной сети D (например, нулевой или полный).Шаг 2.

Строим орграф приращений I ( D,  ).Шаг 3. Если в I ( D, ) вершина v n не достижима из вершины v1 , то  – искомый максимальный поток. В противном случае ищем в I ( D, ) простую цепь  из v1 в vn . Увеличиваем потоки по дугам цепи  на максимально допустимую величину (см. замечание 9.2)a  0 и переходим к шагу 2.Замечание 9.2.

Если дуга x в цепи  имеет то же направление, что и в D, томожно увеличить поток по ней, не превышая ее пропускной способности, т.е. на величину, не превышающую c( x)   ( x). При этом по определению I ( D, ) в этом случаеc( x)   ( x)  0.

Если же дуга x в  направлена противоположно соответствующей дуге xиз D (см. определение I ( D, ) ), то можно увеличить поток по ней (и, соответственно,56уменьшить поток по дуге x ) до обнуления потока по дуге x, т.е. на величину, не превышающую  (x). При этом по определению I ( D, ) в этом случае  ( x)  0. Таким образом,величина a  0, используемая на шаге 3 алгоритма 9.2, является минимальной на множестве натуральных чисел {c( x)   ( x) | x  X , x }  { ( x) | x  X , x }.Разбор типового варианта (продолжение). (в) Используя алгоритм Форда – Фалкерсона, построить максимальный поток для сети D из примера 9.1.Решение. Начинаем с ранее построенного полного потока  3 .

Выделяем в I ( D,3 )простую цепь 4  v1v3v4v2v5 из v1 в v5 . Увеличиваем потоки по дугам из  4 на одинаковую величину, равную 2, до насыщения дуг (v1 , v3 ) , (v3 , v4 ). При этом поток по дуге (v2 , v5 )не превышает ее пропускной способности, а величина потока по дуге (v2 , v4 ) уменьшаетсяна 2 (см. замечание 9.2). В результате поток  3 меняется на поток  4 . На рис. 9.8 приведено изображение орграфа D с потоком  4 . Далее строим орграф приращений I ( D,4 )(см. изображение модифицированного орграфа приращений I ( D,4 ) на рис. 9.9). Поскольку в I ( D,4 ) вершина v5 не достижима из v1 , то согласно алгоритму Форда – Фалкерсона  4 – искомый максимальный поток, при этом 4  21.Рис.

9.8Рис. 9.9Замечание 9.3. Условие единственности источника (стока) не является ограничительным. Например, в случае двух источников v1 , v2 , удовлетворяющих условиям:D 1 (v1 )  , D 1 (v2 )  , можно добавить к транспортной сети D новую вершину v0 идве дуги (v0 , v1 ), (v0 , v2 ). При этом пропускной способностью дуги (v0 , v1 ) (соответственнодуги (v0 , v2 ) ) следует считать сумму пропускных способностей дуг, исходящих из v1 (исходящих из v2 ). В этом случае вершина v0 становится единственным (фиктивным) источником.

Аналогично поступаем в случае большего числа источников или в случае нескольких стоков. Таким образом, приведенные алгоритмы можно использовать и для нахождения максимального потока в транспортных сетях с несколькими источниками и стоками. В этом случае величиной потока в транспортной сети является сумма величин потоков по дугам, исходящим из совокупности ее источников.57БИБЛИОГРАФИЧЕСКИЙ СПИСОК1. Нефедов В.Н., Осипова В.А. Курс дискретной математики.

– М.: Изд-во МАИ,1992.2. Методические указания к выполнению расчетных работ по дискретной математике/ Под ред. В.А. Осиповой. – М.: Изд-во МАИ, 1994.3. Нефедов В.Н. Дискретные задачи оптимизации. – М.: Изд-во МАИ, 1993.58СОДЕРЖАНИЕПредисловие………………………………………………………………….……….…............3Тема 1. Элементы теории графов. Задача об оповещении………………………..…..……....4Тема 2. Матрицы достижимости, связности. Определение наличия контуровв орграфах………………………………………….…………………………………….............9Тема 3.

Поиск маршрутов (путей) в графах (орграфах)….……………………………....….18Тема 4. Деревья и циклы……………………….………………………………………………25Тема 5. Внутренняя и внешняя устойчивость в графах. Ядра графа…..………….…..........27Тема 6. Функции на вершинах орграфа. Порядковая функция. Функция Гранди………....31Тема 7. Хроматическое число графа. Задача об оптимальном окрашивании вершин графа.Задача о минимальном числе помещений для хранения продуктов………………………..36Тема 8. Цикломатическая матрица.

Электрические цепи. Уравнения Кирхгофа………….46Тема 9. Транспортные сети. Поток в сети. Максимальный поток………………………….52Библиографический список………………………………..…………………………..………5859.