2015-03-27
547
Прежде всего, заметим, что реализация алгоритма состоит из конечного числа шагов. В самом деле, п. 3° может применяться лишь конечное число раз, так как на каждом шаге величина потока увеличивается, по крайней мере, на единицу. Вместе с тем величина любого потока не может превзойти суммарной пропускной способности дуг, инцидентных выходу сети 
.
Процесс присвоения меток в силу того, что каждый раз получают метку еще неотмеченные вершины, конечен. И, наконец, в п. 5° поток 
обладает большей величиной, чем 
. Это вытекает из того, что по определению вершины 
и правил п. 4° б) дугам, входящим в , может быть присвоен только знак «+».
Получаемая по правилу 3° функция — поток. Это непосредственно следует из того, что 
— путь. В соответствии с правилом п. 5° строится также поток. Чтобы доказать это утверждение, рассмотрим три соседние вершины последовательности 
. В силу правила 4° б) возможны только ситуации, представленные на рис. 10. Но в этих ситуациях — поток.
Пусть процесс, описанный в п. 4° б), приводит к тому, что вершина не получает метки. Обозначим через 
множество непомеченных вершин. В силу того, что 
, множество определяет разрез сети 
. Каждая дуга 
соединяет помеченную вершину 
с непомеченной вершиной 
. Вершина 
может остаться непомеченной при условии, что 
. Аналогично, на каждой дуге (выходящей из ) выполняется равенство 
, поэтому справедливы соотношения:
.
В силу леммы это означает, что поток обладает наибольшей величиной.
|
Проведенное рассуждение совместно с леммой составляют доказательство следующей теоремы.
Теорема 1: Для заданной транспортной сети величина наибольшего потока равна наименьшей пропускной способности разрезов, т. е. 
.
|
В качестве примера применения алгоритма Форда - Фалкерсона рассмотрим транспортную сеть 
и полный поток , для которого 
(рис. 11). Применяя правила 4° и 5° алгоритма, можно получить поток с величиной 
.
3. Задача о назначении на должность (комбинаторная прикладная задача).
Пусть в некотором учреждении имеется 6 вакантных должностей 
и 6 работников 
.
|
Граф 
, изображенный на рис. 12, иллюстрирует, какие должности может в силу своей квалификации занимать работник . Пусть выполнено условие: каждый работник может занимать хотя бы одну должность и на каждую должность претендует хотя бы один работник. Можно ли произвести назначение на должности так, чтобы все шесть должностей заняли работники соответствующей квалификации?
Один из способов решения этой задачи состоит в рассмотрении вспомогательной транспортной сети . Для ее получения добавим к множеству 
вершин графа еще две вершины: вход 
и выход . Соединим с каждой вершиной 
дугой пропускной способности 
и каждую вершину 
с дугой пропускной способности 
. Припишем дугам исходного графа бесконечные пропускные способности. Получим транспортную сеть , изображенную на рис. 13.
|
Ясно, что если на сети будет существовать поток такой, что 
, то есть поток, насыщающий выходные дуги (одновременно он будет насыщать и входные дуги 
), то требуемое назначение будет возможно произвести. Нужно назначить работника 
на должность в том и только том случае, когда 
.
