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

Поиск K-допустимого разреза высоты (p > 0; случай p = 0 является тривиальным) в алгоритме FlowMap выполняется посредством преобразования <math>N_v \;</math> в ''транспортную сеть'' <math>F_v \;</math> и вычисления потока в этой сети [4] (отсюда и название). Преобразование выполняется следующим образом. Для каждой вершины <math>u \in N_v - \{ v \}, l(u) < p \;</math>, в <math>F_v \;</math> имеются две вершины <math>u_1 \;</math> и <math>u_2 \;</math>, связанные ''мостовым ребром'' <math>\langle u_1, u_2 \rangle</math>; <math>F_v \;</math> содержит единственную ''вершину-сток'' t для всех остальных вершин в <math>N_v \;</math> и единственную ''вершину-источник'' s. Для каждой вершины u из <math>N_v \;</math>, являющейся первичным входом, которая соответствует мостовому ребру <math>\langle u_1, u_2 \rangle</math> в <math>F_v \;</math>, <math>F_v \;</math> содержит ребро <math>\langle s, u_1 \rangle</math>; для каждого ребра <math>\langle u, w \rangle</math> и <math>N_v \;</math> в случае, если и u, и w имеют мостовые ребра в <math>F_v \;</math>, <math>F_v \;</math> содержит ребро <math>\langle u_2, w_1 \rangle</math>; если u имеет мостовое ребро, а w не имеет, <math>F_v \;</math> содержит ребро edge <math>\langle u_2, t \rangle</math>; в противном случае (если ни у одной вершины не имеется мостового ребра) <math>F_v \;</math> не содержит соответствующего ребра. Мостовые ребра имеют единичную пропускную способность; все прочие ребра имеют бесконечную пропускную способность. Если заметить, что каждое ребро в Fv с бесконечной (или единичной) пропускной способностью соответствует вершине <math>u \in N_v \;</math> с l(u) < p и наоборот, и вспомнить теорему о максимальном потоке и минимальном сечении [4], можно показать справедливость следующей леммы.

Зная поток в сети Fv, можно вычислить максимальный поток при помощи алгоритма нахождения дополняющего пути [4]. После вычисления максимального потока оставшийся граф сети потока отключается, и соответствующий минимальный разрез (X, X0) определяется следующим образом: v 2 X0; для и 2 Nv — {v}, если оно является мостовым множеством в Fv и щ может быть достигнуто при помощи поиска в глубину по оставшемуся графу из s, то и 2 X; в противном случае u 2 X0.