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

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

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

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

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

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

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

Очевидно, что 0£j_ij£ с_ij.

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

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

Для любой промежуточной вершины х_i сумма исходящих потоков равна сумме заходящих потоков, т.е. å_jj_ij⁺=å_kj_ik^-.

На рис. 3.29 показана условная сеть, содержащая вершину-исток х₀, вершину-сток х_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	разреза С(Ai)
А1						С0i+ С0j
А2						С0j+Сij+Сik
А3						Сik+Сjk
А4						С0i+Сij+Сjk

 

Например, для разреза А₁ имеем Х’={x₀} и X\Х’={х_i, х_j, х_k}, для А₂ - Х’={х₀, х_i} и X\Х’={х_j, х_k}, для А₃ - Х’={х₀, х_i, x_j} и X\Х’={х_k}, для А₄ - Х’={х₀, х_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, х₁, х₀); (х_k, х₂, х₀); (х_k, х₂, х₃, х₀); (х_k, х₂, х₃, х₁, х₀);

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

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

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

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

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

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

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

⇐ Предыдущая11121314151617181920Следующая ⇒

Поделиться:

Воспользуйтесь поиском по сайту: