4511
правок
Технологическое отображение ППВМ: различия между версиями
Перейти к навигации
Перейти к поиску
Технологическое отображение ППВМ (посмотреть исходный код)
Версия от 11:54, 28 августа 2018
, 28 августа 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 65: | Строка 65: | ||
'''Теорема 1. Если K-допустимый разрез (X, X') v имеет минимальную высоту среди всех K-допустимых разрезов v, то K-покрытие <math>M^*(v) = \{ X' \} + \bigcup \{ M^*(u): u \in input(X') \}</math> имеет минимальную глубину среди всех K-покрытий v.''' | '''Теорема 1. Если K-допустимый разрез (X, X') по v имеет минимальную высоту среди всех K-допустимых разрезов по v, то K-покрытие <math>M^*(v) = \{ X' \} + \bigcup \{ M^*(u): u \in input(X') \}</math> имеет минимальную глубину среди всех K-покрытий v.''' | ||
| Строка 75: | Строка 75: | ||
'''Вычисление K-допустимого разреза минимальной высоты''' | '''Вычисление K-допустимого разреза минимальной высоты''' | ||
Первый этап работы алгоритма FlowMap изначально был назван этапом [[разметка графа|разметки]], так как он включает вычисление метки для каждой вершины K-ограниченного графа. Метка не являющейся первичным входом вершины v, обозначаемая как l(v), определяется как минимальная высота любого разреза по v. Для удобства метки вершин, являющихся первичными входами, считаются равными 0. | |||
Определенные таким образом метки обладают важным свойством ''монотонности''. | |||
'''Лемма 3'''. Пусть <math>p = max \{ l(u): u \in input(v) \} \;</math>. Тогда <math>p \le l(v) \le p + 1 \;</math>. | |||
Заметим, что из этого также следует, что для любой вершины <math>u \in N_v - \{ v \} \;</math> верно <math>l(u) \le p \;</math>. Основываясь на этом наблюдении, для поиска K-допустимого разреза минимальной высоты достаточно проверить, существует ли разрез с высотой p; если нет, то любой K-допустимый разрез будет иметь минимальную высоту (p + 1), и один такой разрез всегда существует для K-ограниченного графа. | |||