4628
правок
Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев: различия между версиями
Перейти к навигации
Перейти к поиску
м
Параллельные алгоритмы вычисления компонент связности и минимальных остовных деревьев (посмотреть исходный код)
Версия от 14:47, 27 марта 2016
, 27 марта 2016→Основные результаты
Irina (обсуждение | вклад) |
Irina (обсуждение | вклад) |
||
| Строка 30: | Строка 30: | ||
Предположим, что B является <math>\lambda</math>-лесом и все его ребра входят в <math>T^*_G \;</math>. Тогда B может быть дополнено для получения <math>2 \lambda</math>-леса при помощи жадного подхода: | Предположим, что B является <math>\lambda</math>-лесом и все его ребра входят в <math>T^*_G \;</math>. Тогда B может быть дополнено для получения <math>2 \lambda</math>-леса при помощи жадного подхода: | ||
Пусть F' – произвольное подмножество F, включающее все деревья <math>T \in F \;</math> с числом вершин меньше <math>2 \lambda</math>. Для любого дерева из F' выберем его минимальное внешнее ребро (т.е. ребро с минимальным весом, соединяющее его с вершиной вне дерева). Обозначим множество таких ребер за B'. Можно показать, что B' состоит только из ребер, принадлежащих к <math>T^*_G \;</math>, а <math>B \cup B' \;</math> является <math>2 \lambda</math>-лесом. Это обстоятельство позволяет найти <math>T^*_G \;</math> за <math>\lfloor log \; n \rfloor</math> шагов следующим образом | Пусть F' – произвольное подмножество F, включающее все деревья <math>T \in F \;</math> с числом вершин меньше <math>2 \lambda</math>. Для любого дерева из F' выберем его минимальное внешнее ребро (т.е. ребро с минимальным весом, соединяющее его с вершиной вне дерева). Обозначим множество таких ребер за B'. Можно показать, что B' состоит только из ребер, принадлежащих к <math>T^*_G \;</math>, а <math>B \cup B' \;</math> является <math>2 \lambda</math>-лесом. Это обстоятельство позволяет найти <math>T^*_G \;</math> за <math>\lfloor log \; n \rfloor</math> шагов следующим образом: | ||
1. <math>B \leftarrow \empty \;</math> | 1. <math>B \leftarrow \empty \;</math> | ||