Введем понятие «разрез» в сети. Разобьем множество вершин графа на два непересекающихся подмножества P и Q, так чтобы вершина истока (например, Х0) находилась в одном подмножестве (например Р), а вершина стока (например, Хn) – в другом подмножестве (например, Q). Разрезом сети (иногда говорят сечением сети) называется совокупность всех дуг, концы которых принадлежат разным подмножествам.
Каждому разрезу поставим в соответствие число С(Р,Q), которое назовем пропускной способностью разреза. Это число строго равно сумме пропускных способностей всех дуг, входящих в разрез, т.е.
С(Р,Q) = 
.
Тогда, величина максимального потока в сети, ни при каких условиях, не может превысить величину пропускной способности минимального разреза, т.е.
w ≤ C(P,Q).
Это и утверждает теорема о максимальном потоке и минимальном разрезе.
Из этой теоремы следует вывод, что, если удастся получить такой поток {z*ij}, величина которого w* окажется равной минимальной пропускной способности некоторого разреза (из всех возможных в сети), то этот поток будет максимальным, а разрез (Р*,Q*) – минимальным разрезом.
Покажем работу этой теоремы на примере задачи с графом, изображенном на рис. 16 (эта задача уже решена методом Форда-Фалкерсона). Требуется получить максимальный поток из вершины Х0 в вершину Х4.
| х1 |
| х2 |
| х3 |
| х4 |
| х0 |
| х3 |
| I |
| I |
Рисунок 16 – Исходный неориентированный граф (разрез I-I)
В этом графе имеется несколько разрезов.
Разрез (I-I) (рис. 16). Пропускная способность разреза
С(I-I) = 3 + 4 + 6 = 13.
Разрез (II-II) (рис. 17). Пропускная способность разреза
С(II-II) = 3 + 2 + 2 + 6 = 13.
| х1 |
| х2 |
| х3 |
| х4 |
| х0 |
| х3 |
| II |
| II |
Рисунок 17 – Исходный неориентированный граф (разрез II-II)
Разрез (III-III) (рис. 18). Пропускная способность разреза
С(II-II) = 3 + 2 + 2 + 3 = 10.
| х1 |
| х2 |
| х3 |
| х4 |
| х0 |
| х3 |
| III |
| III |
Рисунок 18– Исходный неориентированный граф (разрез III-III)
Разрез (IV-IV) (рис.18). Пропускная способность разреза
С(II-II) = 6 + 2 + 3 = 11.
| х1 |
| х2 |
| х3 |
| х4 |
| х0 |
| х3 |
| II |
| IV |
| IV |
Рисунок 19– Исходный неориентированный граф (разрез IV-IV)
Разрез (V-V) (рис.20). Пропускная способность разреза
С(IV-IV) = 3 + 4 + 3 = 10.
| х1 |
| х2 |
| х3 |
| х4 |
| х0 |
| х3 |
| V |
| V |
Рисунок 21 – Исходный неориентированный граф (разрез IV-IV)
Разрез (VI-VI) (рис.21). Пропускная способность разреза
С(II-II) = 6 + 2 + 6 = 14.
| х1 |
| х2 |
| х3 |
| х4 |
| х0 |
| х3 |
| VI |
| VI |
Рисунок 22 – Исходный неориентированный граф (разрез VI-VI)
Таким образом, С(II-II) = min {13;13;10;11;10;14} = 10 условных единиц потока, что равно величине максимального потока, полученной методом Форда -Фалкерсона.
Практическая часть
Задание 4. Вычислить величины максимальных потоков в сети, заданной графом (рис.23,24)(самостоятельно по вариантам, двумя способами – методом Форда -Фалкерсона и по теореме о минимальном разрезе и максимальном потоке)
| х1 |
| х2 |
| х3 |
| х4 |
| х0 |
| х3 |
Рисунок 22 – Исходный неориентированный граф
Таблица вариантов (рис. 22)
| Вариант | ||||||||||||||
| Исток | X0 | X0 | X0 | X1 | X1 | X1 | X2 | X2 | X0 | X2 | X3 | X3 | X3 | X3 |
| Сток | X1 | X2 | X3 | X2 | X3 | X4 | X0 | X1 | X3 | X4 | X0 | X1 | X2 | X4 |
| Вариант | ||||
| Исток | X4 | X4 | X4 | X4 |
| Сток | X0 | X1 | X2 | X3 |
Таблица вариантов (рис.23)
| Вариант | ||||||||||||
| Исток | X0 | X0 | X0 | X0 | X1 | X1 | X1 | X2 | X2 | X2 | X3 | X3 |
| Сток | X1 | X2 | X3 | X4 | X3 | X4 | X2 | X1 | X3 | X4 | X0 | X1 |
| х1 |
| х2 |
| х3 |
| х4 |
| х0 |
| х3 |
Рисунок 23 – Исходный неориентированный граф
Контрольные вопросы:
1. В чем заключается основное достоинство алгоритма Дейкстры? В чем его недостаток?
2. Сформулируйте существо алгоритма Дейкстры
3. Что является критерием окончания действия алгоритма Дейкстры?
4. Что понимается под термином «поток в сети»?
5. Какой поток в сети является максимальным?
6. Сформулируйте существо алгоритма Форда -Фалкерсона.
7. Что понимается под термином «разрез в сети»?
8. О чем гласит теорема о максимальном потоке и минимальном разрезе?
Отчет должен содержать:
1. Тему и цели занятия
2. Ответы на контрольные вопросы (в письменной форме)
3. Выполнение задания 2
4. Выполнение задания 4 (двумя способами)
5. Выводы по каждому заданию
* * *