Ответы на экзаменационные вопросы № 1-31 по курсу "Дискретная математика" (Определение взаимно однозначного соответствия между двумя множествами. Определение транспортной сети, разреза в ней и его пропускной способности. Теорема Форда-Фолкерсона), страница 10

Разрезом данной сети наз. всякое разбиение мн-ва ее вершин на подмн-ва N_S и N_T. Пропускной способностью разреза наз. сумму пропускных способностей всех дуг, ведущих из N_S в N_T. Из сказанного следует, что всякий поток в данной сети может иметь величину не превосходящую пропускных способностей любого из разрезов данной сети. Минимальным разрезом наз. разрез, пропускная способность которого минимальна среди всех разрезов данной сети. Очевидно, что величина макс. потока в сети не превосходит пропускной способности и ее минимального разреза. Отсюда следует, что если некоторый поток в данной сети имеет величину равную пропускной способности какого-либо разреза данной сети, то 1) этот разрез минимален, 2) этот поток максимален.

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

Работа такого алгоритма развертывается по шагам, по завершении шага № t мы получаем поток {a_ij^t} в данной сети. Величины этих потоков при увеличении t монотонно возрастают. Каждый шаг связан с попыткой распространения метки от полюса S к полюсу T. В случае удачи такой попытки величина потока возрастает на величину d³0. В случае невозможности переноса метки в полюс T поток {a_ij^t} оказывается максимальным.

Алгоритм:

0) t=0 a_ij⁰=0 для "i,j

t+1) {a_ij^t} – имеется; Снабжается полюс S меткой. Наша метка из помеченной вершины i переносится в не помеченную вершину j при выполнении одного из двух условий: 1) имеется стрелка из i в j, причем a_ij<c_ij. 2) дуга ведет из непомеченной вершина j в помеченную вершину i, причем a_ij>0. Распространим метку во все вершины, для которых это возможно. В результате этого, выходной полюс T может оказаться помеченным или нет. Рассмотрим обе ситуации: 1) метка достигла полюса T. В этом случае поток {a_ij^t} можно увеличить. Действительно, метка из S в T попала вдоль некоторого неориентированного пути, ведущего из S в T. Для всех дуг этого пути выполняются условия: c_ij-a_ij>0 для согласованно направленных дуг и a_ji>0 для противоположно направленных дуг. Среди левых частей этих неравенств выберем наименьшее и обозначим буквой d. Определим поток {a_ij^t+1}: a_ij^t+1= a_ij^t+d для всех дуг этого пути направленных от S в T. a_ji^t+1=a_ij^t-d для тех дуг этого пути, которые ведут от T в S. Поток во всех остальных дугах остается неизменным. Утверждается, что {a_ij^t+1} – поток. Действительно, 0£ a_ij^t+1£c_ij для любой пары ij. Проверим, что для системы a_ij^t+1 выполняются и законы сохранения во всех вершинах сети. В действительности, такая проверка требуется лишь для вершин входящих в неориентированный путь, вдоль которого была перенесена метка (для всех остальных вершин a_ij^t+1= a_ij^t). Для вершин, лежащих на этом пути, возможна ситуация следующих четырех типов:

Закон сохранения для вершины 2 сохраняется во всех этих случаях. Итак, система чисел a_ij^t+1 также является потоком. Его вершина превосходит величину a_ij^t на d.

Покажем, что если поток {a_ij^t} не допускает увеличения в соответствии с описанным алгоритмом, то этот поток максимален. 2) метка не достигла полюса T. Действительно, в этом случае метку невозможно доставить в T. При этом попытка переноса метки приводит к разрезу сети, если к мн-ву N_S присоединить все вершины, которые удается пометить, а к мн-ву N_T – остальные. Покажем, что величина потока {a_ij^t} равна пропускной способности этого разреза.

Для дуг, пересекающих линию разреза из N_S в N_T, невозможность переноса метки означает равенство a_ij^t=с_ij. Для дуг, пересекающих линию разреза из N_T в N_S: a_ij^t=0. Это означает, что величина потока a_ij^t через данный разрез равна пропускной способности этого разреза. Выше отмечалось, что совпадение величины какого-либо потока с пропускной способностью какого-либо разреза означает минимальность этого разреза и максимальность этого потока, значит {a_ij^t} – поток, максимальный для данной сети. Одновременно доказана и теорема Форда-Фолкерсона: Величина максимального потока в сети равна пропускной способности ее минимального разреза.