4551
правка
Минимальное остовное дерево: различия между версиями
Материал из WEGA
Минимальное остовное дерево (посмотреть исходный код)
Версия от 18:18, 22 декабря 2015
, 22 декабря 2015→Условия оптимальности
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 26: | Строка 26: | ||
'''Свойство сжимаемости'''. Если C – подграф, такой, что для всех пар ребер e и f, имеющих ровно одну конечную точку в C, существует путь <math>P \subseteq C \;</math>, связывающий ef с каждым ребром в P, более легким, чем e или f, в таком случае С является сжимаемым. Для любого сжимаемого подграфа C верно <math>MST(G) = MST(C) \cup MST(G\C) \;</math>. | '''Свойство сжимаемости'''. Если C – подграф, такой, что для всех пар ребер e и f, имеющих ровно одну конечную точку в C, существует путь <math>P \subseteq C \;</math>, связывающий ef с каждым ребром в P, более легким, чем e или f, в таком случае С является сжимаемым. Для любого сжимаемого подграфа C верно <math>MST(G) = MST(C) \cup MST(G \setminus C) \;</math>. | ||
== Базовый жадный алгоритм == | == Базовый жадный алгоритм == | ||
