Теорема 1: Для заданной транспортной сети величина наибольшего потока равна наименьшей пропускной способности разрезов, т. е. .

Рис. 11

В качестве примера применения алгоритма Форда - Фалкерсона рассмотрим транспортную сеть и полный поток , для которого (рис. 11). Применяя правила 4° и 5° алгоритма, можно получить поток с величиной .

 

3. Задача о назначении на должность (комбинаторная прикладная задача).

Пусть в некотором учреждении имеется 6 вакантных должностей и 6 работников .

Рис. 12

Граф , изображенный на рис. 12, иллюстрирует, какие должности может в силу своей квалификации занимать работник . Пусть выполнено условие: каждый работник может занимать хотя бы одну должность и на каждую должность претендует хотя бы один работник. Можно ли произвести назначение на должности так, чтобы все шесть должностей заняли работники соответствующей квалификации?

Один из способов решения этой задачи состоит в рассмотрении вспомогательной транспортной сети . Для ее получения добавим к множеству вершин графа еще две вершины: вход и выход . Соединим с каждой вершиной дугой пропускной способности и каждую вершину с дугой пропускной способности . Припишем дугам исходного графа бесконечные пропускные способности. Получим транспортную сеть , изображенную на рис. 13.

Рис. 13

 

Ясно, что если на сети будет существовать поток такой, что , то есть поток, насыщающий выходные дуги (одновременно он будет насыщать и входные дуги ), то требуемое назначение будет возможно произвести. Нужно назначить работника на должность в том и только том случае, когда .