4511
правок
Рандомизированный алгоритм нахождения минимального остовного дерева: различия между версиями
Перейти к навигации
Перейти к поиску
Рандомизированный алгоритм нахождения минимального остовного дерева (посмотреть исходный код)
Версия от 23:43, 28 апреля 2016
, 28 апреля 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 32: | Строка 32: | ||
1. Хорошо известное [[свойство циклов]] для минимальных остовных деревьев заключается в том, что самое тяжелое ребро любого цикла входного графа G ''не может'' входить в состав минимального остовного дерева. | 1. Хорошо известное [[свойство циклов]] для минимальных остовных деревьев заключается в том, что самое тяжелое ребро любого цикла входного графа G ''не может'' входить в состав минимального остовного дерева. | ||
2. Пусть F – лес графа G (т.е. ациклический подграф G). Ребро <math>e \in E \;</math> называется F-легким, если имеет место один из двух случаев: (1) <math>F \cup \{ e \} \;</math> продолжает оставаться лесом графа G; (2) самое тяжелое ребро цикла, содержащего e, не совпадает с e. Ребро G, не являющееся F-легким, называется F-тяжелым. Отметим, что согласно свойству циклов F-тяжелое ребро не может входить в состав минимального остовного дерева G н''езависимо от того, какой лес F используется''. Пусть имеется лес F графа G. Множество F-тяжелых ребер может быть вычислено за линейное время при помощи простой модификации существующих алгоритмов верификации минимального остовного дерева [6, 12]. | 2. Пусть F – лес графа G (т.е. ациклический подграф G). Ребро <math>e \in E \;</math> называется F-легким, если имеет место один из двух случаев: (1) <math>F \cup \{ e \} \;</math> продолжает оставаться лесом графа G; (2) самое тяжелое ребро цикла, содержащего e, не совпадает с e. Ребро G, не являющееся F-легким, называется F-тяжелым. Отметим, что согласно свойству циклов F-тяжелое ребро не может входить в состав минимального остовного дерева G н''езависимо от того, какой лес F используется''. Пусть имеется лес F графа G. Множество F-тяжелых ребер может быть вычислено за линейное время при помощи простой модификации существующих алгоритмов верификации минимального остовного дерева с линейным временем исполнения [6, 12]. | ||