3.5.4. Поиск максимального потока в сети

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

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

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

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

Объем информации, энергии или вещества, передаваемый в сети от узла x_i к узлу x_j, называют потоком и обозначают _ij.

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

Очевидно, что 0_ij с_ij.

В вершине-истоке х₀ величина потока есть сумма потоков по всем дугам, исходящим из вершины х₀, т.е. =_i_0i⁺.

В вершине-стоке х_k величина потока есть сумма потоков по всем дугам, заходящим в вершину х_k, т.е. =_i_ik^-.

Для любой промежуточной вершины х_i сумма исходящих потоков равна сумме заходящих потоков, т.е. _j_ij⁺=_k_ik^-.

На рис. 3.29 показана условная сеть, содержащая вершину-исток х₀, вершину-сток х_k и две промежуточные вершины х_i и х_j. На каждой дуге в круглых скобках приведены обозначения потока и пропускной способности соответствующей дуги. При этом поток, подводимый к сети равен =(_0i+_0j), поток отводимый от сети равен =(_ik+_jk), поток из вершины х_i в вершину х_j равен _ij. Для вершины х_i имеем _0i=(_ij+_ik), для вершину х_j - _jk=(_0j+_ij).

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

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

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

Например, для разреза А₁ имеем Х’={x₀} и X\Х’={х_i, х_j, х_k}, для А₂ - Х’={х₀, х_i} и X\Х’={х_j, х_k}, для А₃ - Х’={х₀, х_i, x_j} и X\Х’={х_k}, для А₄ - Х’={х₀, х_j} и X\Х’={x_i, х_k}.

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

_max=min{С(A_i)}

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

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

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

Если по дуге (х_s, х_i) возможно увеличение потока ( _si< c_si), то вершину х_i следует пометить +s , что указывает на источник увеличения потока.

Если по дуге (х_i, х_j) возможно увеличение потока  _ij< c_ij, то вершину х_j пометить +i . Это означает, что приращение потока _si пойдет по направлению дуги (х_i, х_j) от вершины х_s.

Если насыщена дуга (х_s, х_i), т.е.  _si=c_si, то метку +s нельзя ставить у вершины х_i. Следовательно, если вершина x_i не помечена, то у вершины x_j нельзя ставить метку +i.

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

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

Если насыщена дуга (х_t, х_j), т.е.  _tj=c_tj, то метку +t нельзя ставить у вершины х_j. Следовательно, если вершина x_j не помечена, то у вершины x_i нельзя ставить метку -j.

Если насыщены обе дуги (х_s, х_i) и (х_t, х_j), что означает невозможность приращения потока  _si и  _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) указаны величина потока и пропускная способность - (_ij, c_ij).

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

хi	шаг итерации
	1	2	3	4	5	6	7
х0	0	0	0	0	0	0	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	шаг итерации
		1	2	3	4	5	6	7
(х0, х1)	2	0	0	1	2	2	2	2
(х0, х2)	1	0	0	0	0	0	1	1
(х0, х3)	3	1	2	2	2	3	3	3
(х1, х3)	4	0	0	1	1	0	0	0
(х1, хk)	3	0	0	0	1	2	2	2
(х2, хk)	2	0	0	1	1	1	2	2
(х3, х2)	1	0	0	1	1	1	1	1
(х3, хk)	2	1	2	2	2	2	2	2

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

В результате выполнения первого шага итерации возможны переходы: _0k={(х_k, х₁, х₀); (х_k, х₂, х₀); (х_k, х₂, х₃, х₀); (х_k, х₂, х₃, х₁, х₀);

(х_k, х₃, х₀); (х_k, х₃, х₁, х₀)}. Пусть выбран _0k=(х_k, х₃, х₀). Приращение потока на =1 проходит по маршруту =((х₀, х₃), (х₃, х_k)).

На втором шаге возможны те же переходы. Пусть выбран переход _0k=(х_k, х₃, х₀). Приращение потока на =1 проходит по маршруту ={(х₀, х₃), (х₃, х_k)}. При этом дуга (х₃, х_k) оказывается насыщенной, т. е. _3k=c_3k=2.

На третьем шага возможны переходы: _0k={(х_k, х₁, х₀); (х_k, х₂, х₀); (х_k, х₂, х₃, х₀); (х_k, х₂, х₃, х₁, х₀)}. Пусть выбран _0k=(х_k, х₂, х₃, х₁, х₀). Приращение потока на =1 проходит по маршруту =((x₀, x₁), (x₁, x₃), (x₃, x₂), (x₂, x_k)). При этом оказывается насыщенной дуга (х₃, х₂), т. е. ₃₂=c₃₂=1.

На четвертом шаге возможны переходы: _0k={(х_k, х₁, х₀); (х_k, х₂, х₀)}. Пусть выбран _ok=(х_k, х₁, х₀). Приращение потока на =1 проходит по маршруту =((x₀, x₁), (x₁, x_k)),. При этом оказывается насыщенной дуга (х₀, х₁), т. е. ₀₁=c₀₁=2.

На пятом шаге возможны переходы: _0k={(х_k, х₁, -x₃, х₀); (х_k, х₂, х₀)}. Пусть выбран _ok=(х_k, х₁, -x₃, х₀). Приращение потока на =1 проходит по маршруту =((x₀, x₃), (x₃, x₁), (x₁, x_k))),. При этом оказывается насыщенной дуга (х₀, х₃), т. е. ₀₃=c₀₃=3.

На шестом шаге возможен только один переход _0k=(х_k, х₂, х₀), так как дуги (x₀, x₁) и (x₀, x₃) насыщены. Приращение потока на =1 проходит по маршруту =((x₀, x₂), (x₂, x_k)),. При этом оказывается насыщенной дуга (х₀, х₂), т. е. ₀₂=c₀₂=1.

На седьмом шаге невозможны ни один переход от x_o к x_k, так как дуги (x₀, x₁), (x₀, x₃) и (х₀, х₂) насыщены и невозможно поставить метки у вершин x₁, x₂, и x₃.