4551
правка
Технологическое отображение ППВМ: различия между версиями
Материал из WEGA
Технологическое отображение ППВМ (посмотреть исходный код)
Версия от 11:34, 28 августа 2018
, 28 августа 2018→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 56: | Строка 56: | ||
Лемма 2. Для K-покрытия M(v) = | '''Лемма 2'''. Для K-покрытия <math>M(v) = \{ C_v \} + \bigcup \{ M(u): u \in input(C_v) \}</math> имеет место <math>d(M(v)) = max \{d(M(u)): u \in input(C_v) \} + 1 \;</math>. | ||
В частности, обозначим за M*(u) K-покрытие вершины u с минимальной глубиной. Тогда d(M(v)) | В частности, обозначим за <math>M^*(u) \;</math> K-покрытие вершины u с минимальной глубиной. Тогда <math>d(M(v)) \ge max \{ d(M^*(u)): u \in input(C_v) \} + 1 \;</math>; равенство имеет место в случае, когда каждое покрытие M(u) в M(v) имеет минимальную глубину. | ||
