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

После того как K-допустимые разрезы минимальной высоты были найдены для всех вершин, каждой вершине оказывается сопоставлен K-допустимый конус <math>C_v \;</math>, определяемый ее разрезом, имеющим минимальную глубину. После этого построение K-покрытия <math>N_M = (V_M, E_M) \;</math> является тривиальным. Во-первых, в <math>V_M \;</math> включаются все вершины, являющиеся первичными выходами. Затем для любого конуса <math>C_v \in V_M \;</math> конус <math>C_u \;</math> для каждой не являющейся первичным входом вершины <math>u \in input(v) \;</math> также включается в <math>V_M \;</math>, равно как и каждая являющаяся первичным входом вершина <math>u \in input(v) \;</math>. Точно так же <math>\langle C_u, C_v \rangle \in E_M</math> для каждой не являющейся первичным входом вершины <math>u \in input(C_v) \;</math>; <math>\langle u, C_v \rangle \in E_M</math> для каждой являющейся первичным входом вершины <math>u \in input(C_v) \;</math>.

'''Лемма 6'''. K-покрытие, построенное вышеописанным образом, является оптимальным по глубине.

Эта процедура линейна по времени, следовательно,

'''Теорема 3. Задача оптимального по глубине технологического отображения для ППВМ на основе таблиц K-LUT на булеву сеть с n вершинами и m ребрами может быть решена за время O(Kmn).'''