Технологическое отображение ППВМ: различия между версиями

'''Лемма''' 4. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети <math>F_v \;</math> не превышает K.

Заметим, что как только величина потока превысит K, вычисление может остановиться, зная, что в этом случае нужного K-допустимого разреза найти не удастся. В этом случае можно модифицировать сеть потока, связав мостами все вершины в Nv - {v}, что позволит включить вершины u с l(u) = p в вычисление разреза, и найти K-допустимый разрез с высотой p+1 аналогичным образом.

Теорема 2. В K-ограниченной булевой сети с n вершинами и m ребрами вычисление K-допустимого разреза минимальной высоты для каждой вершины может быть выполнено за время O(Kmn).

Лемма 5. Разрез (X, X0), вычисленный вышеописанным образом, представляет собой уникальный минимальный разрез максимального объема; более того, если (Y, Y0) – еще один минимальный разрез, то Y0 С X0.

Интуитивно понятно, что разрез большего объема определяет конус большей величины, охватывающий больше логики, в силу чего разрез большего объема является более предпочтительным. Однако заметим, что лемма 5 говорит только о максимуме среди минимальных разрезов; если n(X; X0) < K, то могут существовать другие разрезы, все еще являющиеся K-допустимыми, но имеющие большую величину и больший объем. Алгоритм постобработки, используемый FlowMap, пытается увеличить (X, X0) за счет коллапсирования всех вершин из X0, а также одной или нескольких вершин в сечении, в сток и последующего повторного вычисления потока; это приводит к получению разреза большего объема и оказывается выигрышным, если разрез по-прежнему остается K-допустимым.

Построение K-покрытия