4511
правок
Минимальное остовное дерево: различия между версиями
Перейти к навигации
Перейти к поиску
м
Минимальное остовное дерево (посмотреть исходный код)
Версия от 19:13, 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 – подграф, такой, что для всех пар ребер e и f, имеющих ровно одну конечную точку в C, существует путь <math>P \subseteq C \;</math>, связывающий ef с каждым ребром в P, более легким, чем e или f, в таком случае С является сжимаемым. Для любого сжимаемого подграфа C верно <math>MST(G) = MST(C) \cup MST(G \backslash C) \;</math>. | ||
== Базовый жадный алгоритм == | == Базовый жадный алгоритм == | ||