Технологическое отображение ППВМ: различия между версиями
Перейти к навигации
Перейти к поиску
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 88: | Строка 88: | ||
Поиск K-допустимого разреза высоты (p > 0; случай p = 0 является тривиальным) в алгоритме FlowMap выполняется посредством преобразования | Поиск 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 с бесконечной (или единичной) пропускной способностью соответствует вершине u 2 Nv с l(u) < p и наоборот, и вспомнить теорему о максимальном потоке и минимальном сечении [4], можно показать справедливость следующей леммы. | ||
'''Лемма''' 4. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети | '''Лемма''' 4. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети <math>F_v \;</math> не превышает K. | ||