Программирование на сетях (стр. 2 из 4)
Сеть — это взвешенный граф без циклов и петель, ориентированный в одном направлении от вершины, называемой источником, к вершине, называемой стоком.
На рис. 1.8 представлена сеть. Истоком I является вершина 1, стоком S –вершина 6. Представим, что по ребрам (i,j) сети направляется некоторое вещество (ресурс, информация и т.п.). В скобках указаны пропускные способности ребер. Первое число- это пропускная способность в прямом направлении (от вершины iк вершине j) и второе – в противоположном направлении.
Пропускная способность - максимальное количество вещества rBijB, которое можно пропустить по ребру (i,j). Количество xBijBвещества, проходящего по ребру (i,j) в единицу времени, называется потоком по ребру. Считается, что если есть поток из вершины i в вершину j, то
xBijB = - xBjiB(1.1)
Если поток по ребру (i,j) меньше его пропускной способности, т.е. xBijB< rBijB, то ребро называют ненасыщенным, если xBijB= rBijB, - насыщенным. Совокупность X = {xBijB} потоков по всем ребрам называют потоком по сети или просто потоком.
Поток по ребру не может превысить его пропускной способности, т.е.
(1.2)где n – количество вершин сети.
Приведем основное положение в теории потоков, которое называют условием сохранения потока: для любой вершины, кроме истока I и стока S, количество поступающего вещества в эту вершину, равно количеству вещества, вытекающего из нее. В промежуточных вершинах потоки не создаются и не исчезают.
Математическая запись этого ограничения с учетом формулы (1.1) следующая:
(1.3)Отсюда вытекает, что общее количество вещества, вытекающего из истока I, совпадает с общим количеством вещества, поступающего в сток S, т.е.
(1.4)где j – конечные вершины ребер, исходящих из I;
i – начальные вершины ребер, входящих в S.
Линейную функцию f называют мощностью потока на сети. Сформулируем задачу о максимальном потоке: найти множество XP* P= {xBijPB*P} потоков xBijPB *P по всем ребрам (i,j) сети, которое удовлетворяет условиям (1.1) - (1.3) и доставляет линейной функции (1.4) максимальное значение.
Как видно из формулировки, это типичная задача линейного программирования.
Обратимся к рис. 1.8, где изображена сеть. Для этой сети пропускную способность представим в виде матрицы, используя цифры в скобках. Здесь n = 6 и числа образуют квадратную матрицу шестого порядка (табл. 1.1). Если вершины k и l не соединены, то rBklB= rBlkB = 0. Сформировать матрицу чисел xBijB – это значит задать поток на сети, т.е. найти nP2 Pчисел, удовлетворяющих условиям (1.1) – (1.3). Рассмотрим полный путь 1 – 2 – 5 – 6.
Пропускная способность этого пути не больше 1 ед. и ограничивается ребром (2, 5), которое лежит на этом пути. Поток по этому пути мощностью в 1 ед. будет допустимым, и условии (1.1) – (1.3) должны выполняться для всех вершин и ребер этого пути.
Таблица 1.1
| i/j | 1 | 2 | 3 | 4 | 5 | 6 |
| 1 | 0 | 3 | 6 | 2 | 0 | 0 |
| 2 | 5 | 0 | 0 | 0 | 1 | 0 |
| 3 | 6 | 0 | 0 | 3 | 0 | 4 |
| 4 | 7 | 0 | 9 | 0 | 4 | 0 |
| 5 | 0 | 1 | 0 | 2 | 0 | 5 |
| 6 | 0 | 0 | 1 | 0 | 8 | 0 |
Рис. 1.8
Например, возьмем вершину 2 и проверим условие (1.3):
xB21B + xB25B = (-xB21B) + xB25B = (-1) + 1 = 0.
Представим некоторую сеть. Разобьем множество вершин сети на два непересекающихся подмножества A и B так, чтобы исток I попал в подмножество A, а сток S попал в подмножество B. В результате такого разбиения появляются ребра (i, j), конечные точки которых оказываются в разных подмножествах.
Совокупность ребер (i, j), начальные точки которых принадлежат подмножеству A, а конечные точки – подмножеству B, называют разрезом сети и обозначают A/B.
На рис. 1.9 изображена некоторая сеть. Стрелки указывают положительное направление потока. На сети произведено два разреза: I и II. При разрезе I образовалось два подмножества вершин сети: подмножество A = {1, 2} и B = {3, 4, 5}, а ребрами, образующим разрез, стали (1, 3), (1, 4), (2, 4). При разрезе II образовались подмножества A = {1, 2, 3, 4} и B = {5} с образующими разрез ребрами (3, 5) и (4, 5).
Рис. 1.9
Величина
, представляющая сумму пропускных способностей всех ребер разреза, называется пропускной способностью разреза.Если на сети задан поток X = {xBijB} и разрез (A/B), то величина
, представляющая сумму потоков по всем ребрам разреза, называется потоком через разрез.Дляразреза I R(I) = rB13B + rB14 B+ rB24B = 6 + 2 + 1 = 9. X(I) = xB13B + xB14B + xB24B = 4 + 2 + 0 = 6. Для разреза II – R(II) = 9, X(II) = 6.
В общем случае, если на сети задан поток X = {xij} и произведен разрез (A/B), то хотя бы одно ребро любого полного пути, идущего из истока в сток, будет обязательно принадлежать разрезу (A/B). Напомним, что величина потока по любому полному пути не превышает пропускную способность каждого его ребра, а потому величина X суммарного потока, стремящегося из истока в сток, не может повысить пропускную способность любого разреза сети, т.е.
(1.5)В теории потоков утверждается, что если удастся построить на сети поток XP* P= {xBijPB*P}, величина которого равна пропускной способности некоторого разреза (A/B), то этот поток будет максимальным, а разрез обладать минимальной пропускной способностью. Ниже приводится теорема о максимальном потоке, имеющая большое прикладное значение.
Теорема Форда - Фалкерсона. На любой сети сети максимльная величина потока из истока I в исток S равна максимальной пропускной способности разреза, отделяющего I от S.
6. Алгоритм решения задачи о максимальном потоке
В разделе 4 был проведен расчет мощности потока, но ничего не было сказано о том, будет ли этот поток максимальным. Чтобы ответить на этот вопрос, необходимо исследовать этот поток.
Пусть задан некоторый поток X = {xij}. Разобьем сеть таким образом, чтобы к подмножеству A отошли исток I и все те вершины i, которые достигаются из истока I хотя бы по одному пути, состоящему из ненасыщенных ребер; к подмножеству B отнесем вершины, которые нельзя достичь из истока по ненасыщенным ребрам. При таком разбиении возникают две ситуации:
1) сток
;2) сток
.Рассмотрим случай 1. Если
, то 
Построенное разбиение является разрезом A/B. По условию разбиения для любой вершины
существует путь из истока в i, состоящий из ненасыщенных ребер, а для любой вершины 
такого пути нет. Отсюда следует, что любое ребро (i,j) разреза A/B будет насыщенным (иначе j принадлежало бы A), т.е. xij = rij. Просуммируем все эти равенства по всем 
и всем 
и получим 
(1.6)В этом равенстве слева – величина X потока через разрез, справа – пропускная способность R разреза A/B. Из равенства (1.6) по теореме Форда - Фалкерсона следует, что поток X = {xij} является максимальным.
Рассмотрим случай 2. Если
то существует путь из ненасыщенных ребер, ведущий из истока в сток. По ребрам этого пути можно пропустить дополнительный поток величиной 
, где минимум берется по всем ребрам, входящими в этот путь. Потоки xBijB по всем остальным ребрам остаются без изменения. В результате мощность суммарного потока возрастет на величину 
и это будет новый поток X = {xBijPB1P}.При объединении двух рассмотренных случаев просматривается следующий алгоритм построения максимального потока:
1. Построить некоторый начальный поток XP0P = {xBijPB0P}.
2. Найти подмножество A вершин, достижимых из истока I по ненасыщенным ребрам. Если в этом процессе сток S не попадет в подмножество A, то построенный поток максимальный и задача решена. Если же сток S попал в A, то перейти к п. 3 алгоритма.
3. Выделить путь из истока I в сток S, состоящий из ненасыщенных ребер, и увеличить поток xBijBпо каждому ребру этого пути на величину
, где минимум берется по ребрам (i,j) упомянутого пути. Это означает, что будет построен новый поток XP1P = {xBijPB1P}. После этого надо вернуться к п. 2 данного алгоритма.