Транспортные сети.
Транспортной сетью называется орграф G=(X, U) с множеством вершин X={x1,x2,…,xn} для которого выполняются условия:
1. существует одна и только одна вершина x1 называемая источником, такая, что ни одна дуга не заходит в x1;
2. существует одна и только одна вершина xn, называемая стоком, такая, что из xn не исходит ни одной дуги.
3
.
Каждой дуге и uU
поставлено в соответствии целое число
c(u)0,
называемое пропускной способностью
дуги,
один из возможных потоков
x1 – исток
x2 – сток
x1 и x2 – промежуточная вершина
Вершины в транспортной сети, отличающимся от источника и стока, называется промежуточными.
При каждой дуге в скобках указана ее пропускная способность.
Функция (u), определенная на множестве U дуг транспортной сети G и принимающее целочисленные значения, называется допустимым потоком в транспортной сети G, если:
1. для любой дуги uU величина (u), называемая потоком по дуге и, удовлетворяет условию 0(u)c(u)
2. для любой промежуточной вершине x выполняется равенство
- сумма потоков по дугам, заходящим в u, равно сумме потоков по дугам, исходящей из x.
Величиной потока в транспортной сети G называется величина А, равная сумме потоков по всем дугам, заходящим в xn или, что то же самое, - величина, равная сумме потоков по всем дугам, исходящим из v1.
Пусть - поток в транспортной сети G. Дуга uU называется насыщенной, если поток по ней равен ее пропускной способности, то есть если u)=c(u). Поток называется полным, если любой путь G из u1 в xn содержит, по крайней мере, одну насыщенную дугу.
Поток называется максимальным, если его величина принимает максимальное значение по сравнению с другими допустимыми потоками в транспортной сети G.
Максимальный поток обязательно является полным ( так как в противном случае в G существует некоторая простая цепь из x1 в xn, не содержащая насыщенных дуг, а значит, можно увеличить на 1 потоки по всем дугам из этой цепи и тем самым увеличить на единицу, что противоречит условию максимальности потока.) Но существуют полные потоки, не являющиеся максимальными. Тем не менее, полный поток можно рассматривать как некоторое приближение к максимальному потоку.
Опишем алгоритм построения полного потока в транспортной сети G.
Пусть G=<X, U> - транспортная сеть. Для любого множества x1X такого, что xnX1, xnX1 разрезом сети G относительно множества, вершин x1 называется множество дуг U1={(,v)U | vX1, X1}, то есть множество, включающее в себя все дуги исходящие из вершин, не принадлежащих x1, и заходящие в вершины, принадлежащие x1.
X
1={x2,x3,x4} U1={(x1,x2),(x1,x4),(x1,x3)}
c(U1)=5+2+6=13
X1={x2,x4} U1={(x1,x2),(x1,x4),(x1,x3)}
c(U1)=5+2+8=15
Число
с c(U1)=c(u)
называется пропускной способностью
разреза
.
Разрез с минимальной пропускной
способностью называется минимальным.
Утверждение. Для любого допустимого потока в транспортной сети G и любого множества x1X1, где x1X1, xnX1 вели чина любого допустимого потока в сети G (в том числе и максимального), не превышает пропускной способности любого разреза сети G (в том числе и минимального).
Теорема Форда - Фалкерсона.
величина, максимального потока равна пропускной способности минимального разреза.
Алгоритм нахождения максимального потока в сети.
1. Рисуем граф, совпадающий с исходным (граф приращений). На исходном графе пускаем нулевой поток.
2. Находим на графе приращений путь из источника в сток.
3. Если такого пути нет, то указанный на исходном графе поток является максимальным.
4. По найденному пути пропускаем максимально возможный поток, как на исходном графе, так и на графе приращений. На графе приращений на прямых дугах величину потока отнимаем, на обратных прибавляем (обратные дуги при необходимости добавляются искусственно). Идем к п. 2.
Алгоритм.
Шаг 1. Полагаем uU (u)=0 (то есть начинаем с нулевого потока по всем дугам). Кроме того, полагаем G'=G.
Шаг 2. Уделяем из орграфа G' все дуги, являющиеся насыщенными при потоке в транспортной сети G. Полученный орграф снова обозначим через G.
Шаг 3. Ищем в G простую цепь из x1 в xn. Если такой цепи нет, то искомый полный поток в транспортной сети G. В противном случае переходим к шагу 4.
Шаг 4. Увеличиваем поток (u) по каждой дуге. И из на одинаковую величину a>0 такую, что, по крайней мере, одна дуга из оказывается насыщенной, а потоки по остальным дугам из не превышают их пропускных способностей. При этом величина потока также увеличивается на а, а сам поток в транспортной сети остается допустимым (поскольку в каждую промежуточную вершину, содержащуюся в , дополнительно вошло а единиц потока и из нее вышло также а единиц потока. После этого переходим к шагу 2.
Пример. Построим полный поток в транспортной сети G.
1. Начнем с нулевого потока. Помечаем G'=G.
При нулевом потоке отсутсвуют насыщенные дуги.
2
.
Выделим в G'
простую цепь 1=x1x2x4x6
и увеличим потоки по дугам из 1
на 3 (
до насыщения дуги (x1,
x4)).
В результате получим поток =1;
содержащей одну насыщенную дугу.
3. Пометим ее знаком X (Аналогично будем помечать все другие насыщенные дуги) и удалим из орграфа G'.
Оставшийся орграф снова обозначим через G'.
0
4. Выделим в G' простую цепь.
2=x1x2x3x4x6
и увеличим потоки по дугам из 2
на 2 (до насыщения дуг (x1,x3),(x3,x4)).
В результате получим поток =2,
содержащий 3 насыщенные дуги.
5. Удалим вновь полученные насыщенные дуги из G'. Оставшийся орграф снова обозначим G'.
6
.
Выделим в G
простую цепь 3=x1x3x5x6
и увеличим потоки по дугам 3
на 2 (до насыщения дуги(x3,
x5)).
В результате получим поток =3,
содержащий насыщенные дуги.
7. Удалим вновь полученную дугу из G'. Оставшийся орграф снова обозначим через G':
8. Выделим в G' простую цепь 4=x1x2x5x6 и увеличим потоки по дугам из 4 на 2 (до насыщения дуги (x1x2)) В результате получим поток =4, содержащий 5 насыщенных дуг:
9
.
Удалим вновь полученную насыщенную
дугу из G. Оставшийся орграф снова
обозначим через G':
10. Заметим, что в G' не существует пути из x1 в x6, а следовательно, в транспортной сети G с потоком 4 не существует пути из x1 в x6, который не содержал бы насыщенных дуг, то есть поток 4 является полным. Величина4 полученного полного потока равна 9.
Найти полные потоки в транспортных сетях.
