Метод дробления шага 5 страница

и после преобразования имеем c₄₆=3, c₅₆=0.

Итерация 6. В вершину 6 ведет дуга нулевой длины из вершины 5, поэтому помечаем ее числом m₆= 5. Поскольку мы отметили конечную вершину маршрута, то алгоритм завершен и мы можем, используя значения отметок для родителей, выписать искомый кратчайший путь (1,3,5,6).

1 3(4)

10

2 2

0 5

L_min=9 ед.

(2)1 6 2

Следует также добавить, что если бы наш выбор на итерациях 3 и 5 был иным, то мы получили бы альтернативные, пути той же длины (1,2,3,5,6), т.е. рассмотренная задача имеет несколько решений.

34. Алгоритм Форда-Фалкерсона.

Введём некоторые обозначения:

Пропускная способность дуги – некоторое положительное b_ij число, поставленное в соответствие дуге (v_i, v_j).

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

-v, если v_j =s;

∑x_ij - ∑x_jk = 0, если v_j ≠ s, v_j ≠ t;

_{i k}

v, если v_j = t;

v ≥ 0; 0≤x_ij≤b_ij для всех i, j

Здесь:

а) x_ij – поток между вершинами v_i и v_j

b) x_kj - поток между вершинами v_i и v_k

c) первую сумму берут по дугам, ведущим в вершину v_j,

d)вторую сумму берут по дугам, ведущим из вершину v_j

Неотрицательное число v называют величиной потока. Число x_ij называют потоком по дуге (v_i, v_j) или дуговым потоком. Ограничения выражают тот факт, что в каждую вершину (кроме источника и стока) приходит столько потока, сколько из него уходит (условие сохранения потока), и что поток x_ij по дуге ограничен пропускной способностью дуги b_ij.

Обозначим через F_st множество неотрицательных чисел x_ij, удовлетворяющих поставленным ограничениям. Будем называть путь из S в t увеличивающим поток F_st, если x_ij<b_ij на всех прямых дугах и x_ji>0 на всех обратных дугах этого пути. Поток F_st максимален тогда и только тогда, когда не существует пути, увеличивающего поток F_st. Величина максимального потока в любой сети принимает, безусловно, единственное значение. Ну может существовать несколько различных максимальных потоков F_st, имеющих одинаковую величину.

Пусть задана ориентированная сеть с одним источником S и одним стоком t и пусть дуги (v_i, v_j) имеют ограниченную пропускную способность. Задача о максимальном потоке заключается в поиске таких потоков по дугам, что результирующий поток, протекающий из источника S в сток t, является максимальным. Задача о максимальном потоке может быть сформулирована как задача линейного программирования, и поэтому может быть решена симплекс – методом. Однако для её решения можно применить более эффективный метод – метод расстановки пометок (метод разработан Фордом и Фалкерсоном).

Алгоритм начинает работу с некоторого допустимого решения, вершины рассматривает как промежуточные пункты передачи потока, а дуги – пометки и увеличивающие (аугментальные) пути потока. Пометку вершину используют для указания как величины потока, так и источника потока, вызывающего изменениетекущего потока по дуге, соединяющий этот источник с рассматриваемой вершиной. Если q_i единиц потока посылают из вершины v_i в вершину v_j и это вызывает увеличение потока по этой дуге, то будем говорить, что вершина v_j помечена из вершиныv_i символом (+ q_i); в данном случае вершине v_j приписывают пометку [+q_i; v_i]. Если посылка q_i единиц потока вызывает уменьшение потока по дуге, то будем говорить, что вершина v_j помечена из вершины v_i символом(-q_j). В таком случае вершине приписывают пометку [-q_i;v_i].

Текущий поток из вершины v_i в вершину v_j увеличивается, когда q_j единиц дополнительного потока посылается в вершину v_j по ориентированной дуге (v_i, v_j) в направлении, совпадающем с её ориентацией. В таком случае дугу называют прямой. Если q_i единиц дополнительного потока посылаются в вершину v_j по ориентированной дуге (v_j; v_i), т.е. в направлении, противоположном её ориентации, то текущий поток из v_j в v_i уменьшается, а дугу (v_j; v_i) называют обратной. Вершина v_j может быть помечена из вершины v_i только после того, как вершине v_i приписана пометка. Если вершина v_j помечена из вершины v_i и дуга (v_i, v_j) прямая, тот поток по данной дуге увеличивается, и величина, соответствующая оставшейся неиспользованной пропускной способности дуги, должна быть нужным образом скорректирована. Если некоторой вершине приписывают пометку и при этом используют прямую ветвь, то она может иметь только остаточную пропускную способность.

Увеличивающий (аугментальный) путь потока из S в t определяют как связанную последовательность прямых и обратных дуг, по которым из S в t можно послать несколько единиц потока. Поток по каждой прямой дуге увеличивается, при этом не превышает её пропускной способности, а поток по каждой обратной дуге уменьшается, оставаясь при этом неотрицательным. Аугментальный путь потока используют для выбора такого способа изменения потока, при котором поток в узле t увеличивается, и для каждого внутреннего узла сети при этом не будет нарушено условие сохранения потока.

Как конкретно можно увеличить поток на q_j единиц? Предположим, что дуге (v_i, v_j) уже приписан поток x_ij ≥ 0; причем x_ij ≤ b_ij - пропускная способность дуги (v_i, v_j). Величина q_i не может превосходить остаточной пропускной способности b_ij – x_ij. Но из вершины v_i не всегда можно получить b_ij – x_ij единиц потока. Отметим, что в вершину v_j можно послать столько единиц потока, сколько их добавляется в вершину v_i, т. е. самое большое q_i. Следовательно, поток по прямой дуге (v_i, v_j) можно увеличить на q_i = min[q_i, x_ij-b_ij]. Аналогично получается для вершины, если дуга (v_j, v_i) является обратной. Уменьшение потока по дуге (v_j, v_i) возможно только в том случае, когда x_ji ≥ 0. поток может быть уменьшен самое большее на число единиц потока, которые можно взять из вершины v_i т. е. на q_i. Следовательно, поток по обратной дуге (v_j, v_i) может быть уменьшен на q_j=min[q_i; x_ji].

В начале работы алгоритма источнику приписывают пометку [∞;-], указывающую на то, что из данной вершины может вытекать поток бесконечно большой величины. Далее мы ищем аугментальный путь потока от источника к стоку, проходящему через помеченные вершины. Все вершины (за исключением источника) в начальный момент не помечены. Пытаясь достичь стока, мы проходим, выбирая дуги с наибольшими пропускными способностями, по прямым и обратным дугам и последовательно помечаем принадлежащие им вершины. Возможны два случая:

1. стоку приписывают пометку [+q;k], k-номер вершины, связанный со стоком. В этом случае аугментальный путь потока найден и поток по каждой дуге этого пути может быть увеличен или уменьшен на q_t. После изменения дуговых потоков текущие пометки стирают и всю описанную процедуру повторяют заново.

2. сток t не может быть помечен. Этот означает, что аугментальный путь потока не может быть найден. Следовательно, построенные дуговые потоки образуют оптимальное решение (максимальный поток).

Задача.

Найти максимальное количество информации, которое может быть передано из источника S в сток t по сети, представленной на рисунке 1. Пропускные способности дуг b_ij отмечены.

4 рис.1 Исходные данные для задачи о максимальном

потоке (о максимальном 2 количества информации).

2 3

1 2