4551
правка
Технологическое отображение ППВМ: различия между версиями
Материал из WEGA
Технологическое отображение ППВМ (посмотреть исходный код)
Версия от 11:50, 12 сентября 2018
, 12 сентября 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 91: | Строка 91: | ||
'''Лемма''' | '''Лемма 4'''. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети <math>F_v \;</math> не превышает K. | ||
| Строка 97: | Строка 97: | ||
Заметим, что как только величина потока превысит K, вычисление может остановиться, зная, что в этом случае нужного K-допустимого разреза найти не удастся. В этом случае можно модифицировать сеть потока, связав мостами все вершины в | Заметим, что как только величина потока превысит K, вычисление может остановиться, зная, что в этом случае нужного K-допустимого разреза найти не удастся. В этом случае можно модифицировать сеть потока, связав мостами все вершины в <math>N_v - \{ v \} \;</math>, что позволит включить вершины u с l(u) = p в вычисление разреза, и найти K-допустимый разрез с высотой p + 1 аналогичным образом. | ||
| Строка 103: | Строка 103: | ||
Теорема 2. В K-ограниченной булевой сети с n вершинами и m ребрами вычисление K-допустимого разреза минимальной высоты для каждой вершины может быть выполнено за время O(Kmn). | '''Теорема 2. В K-ограниченной булевой сети с n вершинами и m ребрами вычисление K-допустимого разреза минимальной высоты для каждой вершины может быть выполнено за время O(Kmn).''' | ||
| Строка 109: | Строка 109: | ||
Лемма 5. Разрез (X, | '''Лемма 5'''. Разрез (X, X'), вычисленный вышеописанным образом, представляет собой уникальный минимальный разрез максимального объема; более того, если (Y, Y') – еще один минимальный разрез, то <math>Y' \subseteq X'</math>. | ||
Интуитивно понятно, что разрез большего объема определяет конус большей величины, охватывающий больше логики, в силу чего разрез большего объема является более предпочтительным. Однако заметим, что лемма 5 говорит только о максимуме среди минимальных разрезов; если n(X | Интуитивно понятно, что разрез большего объема определяет конус большей величины, охватывающий больше логики, в силу чего разрез большего объема является более предпочтительным. Однако заметим, что лемма 5 говорит только о максимуме среди минимальных разрезов; если n(X, X') < K, то могут существовать другие разрезы, все еще являющиеся K-допустимыми, но имеющие большую величину и больший объем. Алгоритм постобработки, используемый FlowMap, пытается увеличить (X, X') за счет коллапсирования всех вершин из X', а также одной или нескольких вершин в сечении, в сток и последующего повторного вычисления потока; это приводит к получению разреза большего объема и оказывается выигрышным, если разрез по-прежнему остается K-допустимым. | ||
Построение K-покрытия | '''Построение K-покрытия''' | ||
После того как K-допустимые разрезы минимальной высоты были найдены для всех вершин, каждой вершине оказывается сопоставлен K-допустимый конус Cv, определяемый ее разрезом, имеющим минимальную глубину. После этого построение K-покрытия NM = (VM, EM) является тривиальным. Во-первых, в VM включаются все вершины, являющиеся первичными выходами. Затем для любого конуса Cv 2 VM конус Cu для каждой не являющейся первичным входом вершины u 2 input(v) также включается в VM, равно как и каждая являющаяся первичным входом вершина u 2 input(v). Точно так же hCu; Cvi 2 EM для каждой не являющейся первичным входом вершины u 2 input(Cv); hu; Cvi 2 EM для каждой являющейся первичным входом вершины u 2 input(Cv). | После того как K-допустимые разрезы минимальной высоты были найдены для всех вершин, каждой вершине оказывается сопоставлен K-допустимый конус Cv, определяемый ее разрезом, имеющим минимальную глубину. После этого построение K-покрытия NM = (VM, EM) является тривиальным. Во-первых, в VM включаются все вершины, являющиеся первичными выходами. Затем для любого конуса Cv 2 VM конус Cu для каждой не являющейся первичным входом вершины u 2 input(v) также включается в VM, равно как и каждая являющаяся первичным входом вершина u 2 input(v). Точно так же hCu; Cvi 2 EM для каждой не являющейся первичным входом вершины u 2 input(Cv); hu; Cvi 2 EM для каждой являющейся первичным входом вершины u 2 input(Cv). | ||
