Дальнейший анализ: количество глобальных минимальных разрезов

Анализ алгоритма стягивания дает на удивление простой ответ на следующий вопрос: имеется ненаправленный граф G = (V, E) с n узлами, какое максимальное количество глобальных минимальных разрезов он может иметь (как функции от n)?

Тогда s в сочетании с любым подмножеством {v1, v2, …, vn} образует сторону источника в минимальном разрезе, а следовательно, всего существуют

2n минимальных разрезов s–t.

Но в том, что касается глобальных минимальных разрезов в ненаправленном графе, ситуация выглядит совершенно иначе. Немного поэкспериментировав на примерах, вы убедитесь в том, что цикл из n узлов имеет  глобальных минимальных разрезов (полученных разрезанием любых двух ребер), и на первый взгляд неясно, как построить ненаправленный граф с большим количеством.

Сейчас мы покажем, что анализ алгоритма стягивания немедленно дает ответ на этот вопрос и доказывает, что цикл из n узлов в действительности является крайним случаем.

(13.6) Ненаправленный граф G = (V,E) из n узлов содержит не более    глобальных минимальных разрезов.

Доказательство. В доказательстве (13.5) установлено даже больше, чем заявлено в утверждении. Допустим, имеется граф G, а C1, …, Cr — все его глобальные минимальные разрезы. Пусть i обозначает событие «Ci возвращается алгоритмом стягивания», а  — событие «алгоритм возвращает любой глобальный минимальный разрез».

Тогда, хотя в  (13.5) просто утверждается, что,  доказательство фактически демонстрирует, что для всех i выполняется. События в паре и являются взаимоисключающими (так как при любом выполнении алгоритма возвращается только один разрез), поэтому, согласно границе объединения для взаимоисключающих событий (13.49), имеем.