Теория и методы принятия решений

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

минимальным разрезом транспортной сети называется разрез с минимальной пропускной способностью.

Пример. Транспортная сеть

имеет два разреза и . Пропускная способность первого разреза равна 11 (7+4), а второго – 9 (4+5), поэтому максимальный поток в этой транспортной сети равен 9 = min(11, 9). Этот максимальный поток указан в круглых скобках.

4.1. Алгоритм построения максимального потока в транспортной сети

Цепью, соединяющей исток A0 со стоком An, (или просто цепью) в транспортной сети называется последовательность дуг A0A1, …, An‑1 An, в которой вершина Ai является началом i-ой дуги, а вершина Ai+1 – её концом (или, наоборот, Ai является концом i-ой дуги, а вершина Ai+1 – её началом).

Например, в следующей сети с заданным в скобках потоком

цепями являются последовательности AB, BC, CD и AC, CB, BD, причём в первой цепи направление дуги BC совпадает с направлением потока, а во второй цепи направление дуги CB противоположно направлению потока.

Определение. Дуга цепи называется допустимой дугой, если:

1. направление дуги совпадает с направлением потока и поток по этой дуге меньше её пропускной способности;
2. направление дуги противоположно направлению потока и поток по этой дуге больше нуля.

Цепь, соединяющая исток сети со стоком, называется увеличивающей, если все её дуги являются допустимыми.

Алгоритм построения максимального потока в сети

1. Если поток в сети не задан,

то считать поток нулевым.

2. Пока в сети есть увеличивающие цепи повторять:

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

3. Если в сети нет увеличивающих цепей,

то максимальный поток построен,

Пример 1 (Поток в сети не задан). Построить максимальный поток для заданной транспортной цепи.

Решение.

1. Поток в сети не задан, считаем его нулевым.

2. Пока в сети есть увеличивающие цепи, повторяем: