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

Вспомним, что <math>C_v \;</math> определяет K-допустимый разрез (X, X'), где <math>X' = C_v, X = N_v - C_v \;</math>. Обозначим за H(X, X') ''высоту'' разреза (X, X'), определяемую как <math>H(X, X') = max \{ d(M^*(u)): u \in input(X') \} + 1 \;</math>. Очевидно, что H(X, X') обеспечивает минимальную глубину для любого K-покрытия вершины v, содержащего <math>C_v = X' \;</math>. Кроме того, за счет подходящего выбора разреза можно минимизировать высоту H(X, X'), что позволяет получить K-покрытие с минимальной глубиной:

'''Теорема 1. Если K-допустимый разрез (X, X') v имеет минимальную высоту среди всех K-допустимых разрезов v, то K-покрытие <math>M^*(v) = \{ X' \} + \bigcup \{ M^*(u): u \in input(X') \}</math> имеет минимальную глубину среди всех K-покрытий v.'''

По определению, высота разреза зависит от (глубин) K-покрытий с минимальной глубиной вершин из множества <math>N_v - \{ v \} \;</math>. Для этого можно использовать процедуру ''динамического программирования'', следующую топологическому порядку, так что к моменту, когда необходимо определить K-покрытие v с минимальной глубиной, K-покрытие каждой вершины из <math>N_v - \{ v \} \;</math> с минимальной глубиной уже известно, и высоту разреза можно легко определить. Именно так работает первый этап алгоритма FlowMap.