Разбиение схемы: сбалансированный подход с минимальным разрезом на базе сетевого потока: различия между версиями

Перейти к навигации Перейти к поиску
Строка 38: Строка 38:




Процедура: инкрементное вычисление потока
Процедура инкрементного вычисления потока


1. пока 9 добавочный дополняющий путь из s в t, увеличить значение потока вдоль дополняющего пути;
  1. '''while''' <math>\exists</math> добавочный дополняющий путь из s в t, увеличить значение потока вдоль дополняющего пути;
 
 
2. пометить все вершины u s.t. 9 дополняющий путь из s в u;
  2. пометить все вершины u, такие, что <math>\exists</math> дополняющий путь из s в u;
 
 
3. пусть C0 – множество мостовых ребер, начальные вершины которых помечены, а концевые – не помечены;
  3. пусть C' – множество мостовых ребер, начальные вершины которых помечены, а концевые – не помечены;
 
 
4. вернуть сетки, соответствующие мостовым ребрам в C0, в качестве минимального сетевого разреза C, а помеченные вершины – в качестве X.
  4. вернуть сетки, соответствующие мостовым ребрам в C', в качестве минимального сетевого разреза C, а помеченные вершины – в качестве X.




Источник — http://pco.iis.nsk.su/wega/index.php/Разбиение_схемы:_сбалансированный_подход_с_минимальным_разрезом_на_базе_сетевого_потока