Программирование на сетях

Математическая запись этого ограничения с учетом формулы (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 не соединены, то rBkl B= rB lkB = 0. Сформировать матрицу чисел xBijB – это значит задать поток на сети, т.е. найти nP2 Pчисел, удовлетворяющих условиям (1.1) – (1.3). Рассмотрим полный путь 1 – 2 – 5 – 6.

Пропускная способность этого пути не больше 1 ед. и ограничивается ребром (2, 5), которое лежит на этом пути. Поток по этому пути мощностью в 1 ед. будет допустимым, и условии (1.1) – (1.3) должны выполняться для всех вершин и ребер этого пути.

Таблица 1.1

Рис. 1.8

Например, возьмем вершину 2 и проверим условие (1.3):

xB21B + xB25B = (-xB21B) + xB25B = (-1) + 1 = 0.

5. Разрез на сети

Представим некоторую сеть. Разобьем множество вершин сети на два непересекающихся подмножества 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) сток .

 Скачать реферат