4430
правок
Технологическое отображение ППВМ: различия между версиями
Перейти к навигации
Перейти к поиску
м
Технологическое отображение ППВМ (посмотреть исходный код)
Версия от 12:08, 28 августа 2018
, 28 августа 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 86: | Строка 86: | ||
Заметим, что из этого также следует, что для любой вершины <math>u \in N_v - \{ v \} \;</math> верно <math>l(u) \le p \;</math>. Основываясь на этом наблюдении, для поиска K-допустимого разреза минимальной высоты достаточно проверить, существует ли разрез с высотой p; если нет, то любой K-допустимый разрез будет иметь минимальную высоту (p + 1), и один такой разрез всегда существует для K-ограниченного графа. | Заметим, что из этого также следует, что для любой вершины <math>u \in N_v - \{ v \} \;</math> верно <math>l(u) \le p \;</math>. Основываясь на этом наблюдении, для поиска K-допустимого разреза минимальной высоты достаточно проверить, существует ли разрез с высотой p; если нет, то любой K-допустимый разрез будет иметь минимальную высоту (p + 1), и один такой разрез всегда существует для K-ограниченного графа. | ||
Поиск K-допустимого разреза высоты (p > 0; случай p = 0 является тривиальным) в алгоритме FlowMap выполняется посредством преобразования Nv в транспортную сеть Fv и вычисления потока в этой сети [4] (отсюда и название). Преобразование выполняется следующим образом. Для каждой вершины u 2 Nv - {v}, l(u) < p, в Fv имеются две вершины u1 и u2, связанные мостовым ребром hu1;u2i; Fv содержит единственную вершину-сток t для всех остальных вершин в Nv и единственную вершину-источник s. Для каждой вершины u из Nv, являющейся первичным входом, которая соответствует мостовому ребру («ь мг) в Fv, Fv содержит ребро hs;u1i; для каждого ребра hu; wi и Nv в случае, если и u, и w имеют мостовые ребра в Fv, Fv содержит ребро hu 2 ;w1 i; если u имеет мостовое ребро, а w не имеет, Fv содержит ребро edge hu2 ; ti; в противном случае (если ни у одной вершины не имеется мостового ребра) Fv не содержит соответствующего ребра. Мостовое ребро имеет единичную пропускную способность; все прочие ребра имеют бесконечную пропускную способность. Если заметить, что каждое ребро в Fv с бесконечной (или единичной) пропускной способностью соответствует вершине u 2 Nv с l(u) < p и наоборот, и вспомнить теорему о максимальном потоке и минимальном сечении [4], можно показать справедливость следующей леммы. | |||
'''Лемма''' 4. Вершина v содержит K-допустимый разрез высоты p в том и только том случае, если значение максимального потока в сети Fv не превышает K. | |||