4.2. Конденсация вершин

Предположим, что для графа решена задача о максимальном потоке (от s к t), причем две случайным образом выбранные вершины. Пусть минимальный разрез, соответствующий максимальному потоку, и рассмотрим две вершины лежащие обе в (или обе лежащие в Если мы теперь хотим найти максимальный поток из то все вершины из если могут быть «сконденсированы» в одну вершину коль скоро речь идет только о вычислении потока. Эта кондепсация такова, что ребра заменяются ребрами и любые параллельные ребра между одной и, той же парой вершин (которые могут получиться) заменяются единственным ребром, пропускная способность которого равна сумме пропускных способностей параллельных ребер. На рис. иллюстрируется процесс конденсации. Тот факт, что такая конденсация множества возможна, был установлен Гомори и Ху [14, 16], развившими вышеописанный нами метод. В доказательстве показывается, что все вершины должны лежать с одной и той же стороны от минимального разреза отделяющего от (т. е. или или так что внутренние свойства подграфа графа не влияют на вычисление минимального разреза между