6.2. Активные циклы

Так как цикл можно рассматривать как маршрут с совпадающими начальной и конечной вершинами, то выигрыш цикла и его пропускная способность могут быть определены так же, как и для маршрута. Цикл называется активным в графе по отношению к вершине если

(I) его выигрыш больше единицы,

(II) его инкрементальная пропускная способность отлична от нуля,

(III) на имеется некоторая вершина для которой существует аугментальный маршрут от

Активный по отношению к начальной вершине цикл может быть определен аналогично. Из вышеприведенного определения ясно, что с помощью циркуляции потока по активному циклу можно создать дополнительный поток (по свойству и передать его в вершину свойству В вышеприведенном примере на рис. 11.16(b) поток порождался циркуляцией по активному циклу

Активный по отношению к цикл называется дезактивированным, если добавление дополнительного потока в осуществлено так, что или инкрементальная пропускная способность цикла уменьшилась до нуля, или пропускные способности всех аугментальных цепей от какой-либо вершины на цикле до вершины уменьшились до нуля (т. е. в новом графе не может быть сделано больше никакого добавления ненулевого дополнительного потока). В [13] и [22] доказаны следующие утверждения.

Теорема 7. Поток В является оптимальным тогда и только тогда, когда граф не содержит никаких активных циклов по отношению к или

Теорема 8. Пусть является оптимальным потоком. Тогда если поток увеличить по какой-либо (от аугментальной цепи с наивысшим выигрышем, то вновь полученный поток также будет оптимал ьным.

Теорема 9. Поток В будет оптимально-максимальным, если некоторый разрез отделяющий от является насыщенным и если не существует никакого активного цикла по отношению к все вершины которого лежат в