4551
правка
Минимальное остовное дерево: различия между версиями
Материал из WEGA
Минимальное остовное дерево (посмотреть исходный код)
Версия от 19:32, 22 декабря 2015
, 22 декабря 2015→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 47: | Строка 47: | ||
'''Приближенная сжимаемость'''. Рассмотрим граф G', полученный из G при помощи увеличения веса некоторых ребер. Если C является сжимаемым относительно G', то <math>MST(G) = MST(MST(C) \cup MST(G \backslash C) \cup E^*) \;</math>, где E* – множество ребер с увеличенными весами. | '''Приближенная сжимаемость'''. Рассмотрим граф G', полученный из G при помощи ''увеличения'' веса некоторых ребер. Если C является сжимаемым относительно G', то <math>MST(G) = MST(MST(C) \cup MST(G \backslash C) \cup E^*) \;</math>, где E* – множество ребер с увеличенными весами. | ||
