Главная  Полное построение алгоритма 

[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [ 91 ] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

Из примера на рис. 5.5.1 видно, что если бы мы так сделали, то могли бы выбрать нежелательный цикл из ребер, например для vt выбрать 612, для Vi выбрать е, для выбрать ej. Мы могли бы также выбрать для Wj, для и 632 для Vg. Одновременно выбранные ребра показаны жирными линиями.

Однако если мы выберем для каждой вершины Vt то из ребер наименьшего веса, которое инцидентно вершине Vj Цфг) с наименьшим индексом, то мы исключим возможность циклов. Чтобы показать


Рис. 5.5.1. Цикл из ребер, полученный одновременным выбором в каждой вершине любого ребра с наименьшим весом.

ЭТО, предположим, что Vt, Vj, v, Vt - цикл, выбранный этим способом, т. е. вц выбрано для Vt, е выбрано для Vj, а е; выбрано для w. Предположим, что t -наименьший индекс среди i, j, k. Отсюда следует, что вес WtjWj, так как если Wij<.Wjf,, то вц было бы выбрано для Vj. По тем же причинам Wjwi и wWij. Таким образом, все веса должны быть равны. Если это так, то вц должно быть выбрано для Vi, так как i - наименьший индекс. Это противоречит нашему предположению, что Cj выбрано для Vj. Аналогичные рассуждения можно провести для цикла из любого числа ребер.



Рис. 5.5.2. Остовное дерево, полученное одновременным выбором ребер, имеющих наименьший вес и наименьший индекс.

На рис. 5.5.2 показаны ребра, которые были бы выбраны при такой модификации. Отметим, что это правило не только позволяет нам отыскать остовное дерево в G за один «параллельный» шаг, но




• 7 1 6

Рис. 5.5.3. Сеть, требующая более чем одного параллельного шага для отыскания остовного дерева минимального веса.

это дерево имеет минимальный вес! Сеть G на рис. 5.5.3, однако, показывает, что такой параллельный алгоритм не всегда оказывается настолько быстрым.

Теперь предложим алгоритм, принадлежащий Соллину и являющийся простой модификацией описанной процедуры.

Algorithm SOLLIN. Для отыскания остовного дерева Т минимального веса во взвешенной связной сети G с М вершинами Vi, V, . . ., V ц. N ребрами.

Шаг 1. [Выбор ребер с наименьшим весом.] Выбирается одновременно для каждой вершины V bG ребро с наименьшим весом, инцидентное V; if одинаковый наименьший вес имеют два или более ребер, инцидентных Fthen выбрать

ребро, соединяющее V с вершиной, обладающей наименьшим индексом fi; set /С-«-число уже выбранных ребер. Шаг 2. [Выбраны уже М-1 ребер?] While /С<М-1 do шаг 3 od; and STOP.

Шаг 3. [Выбор ребер между поддеревьями]. Пусть Ti, Т, . . ., обозначают поддеревья G, образуемые выбранными к данному моменту ребрами; одновременно выберем для каждого поддерева Ti ребро с наименьшим весом между некоторой вершиной в Г; и любым другим поддеревом Tj\ if одинаковым наименьшим весом обладают два или более ребер, скажем {Vp, и Vs), then выбрать ребро по следующему правилу, предполагая P<.Q и R<.S: if P<R then выбрать (Vp, 1Л) fi; if R<P then выбрать {V,, I/5) fi; ii P=R then if Q<S then выбрать {Vp, Vq) else выбрать {V,, V) fi fi;

set К число уже выбранных ребер.

Прежде чем комментировать правильность и сложность алгоритма Соллина, проиллюстрируем его на примере.

Применив шаг 1 алгоритма к сети G на рис. 5.5.3, мы обнаружим четыре поддерева Ти Т, Т и Т на рис. 5.5.4. Три ребра (ej,, е и 63), соединяющие Т с другим деревом, имеют одинаковый вес (2); из этих ребер мы выберем ej,, так как 2 - наименьший индекс. Для Т выбор производится между е„ и е; мы выбираем е, так как 3 - наименьший



индекс. Для выбор происходит между е,2, е и е; выбираем е,2. Наконец, для Ti из е и выбираем е- Таким образом, после однократного применения шага 3 мы получаем остовное дерево минимального веса, приведенное на рис. 5.5.5.

Чтобы установить правильность алгоритма SOLLIN, достаточно показать справедливость следующих утверждений:

Однократное применение шага 1 дает лес.

3 -о

Рис. 5.5.4. Поддеревья сети с рис. .5.6.3, сформированные алгоритмом SOLLIN за один шаг.


Рис. 5.5.5. Остовное дерево минимального веса, найденное алгоритмом SOLLIN за два шага.

Если множество ребер, выбранных до шага 3, образует лес, то это же верно для множества ребер, выбранного после шага 3.

Шаг 3 (и шаг 1) выбирает по крайней мере одно ребро; это гарантирует, что алгоритм SOLLIN завершит работу за конечное число шагов.

Если эти утверждения верны, то можно утверждать, что алгоритм SOLLIN находит остовное дерево Т. Остается только показать, что:

Остовное дерево Т, найденное алгоритмом SOLLIN, имеет минимальный вес.

Доказательства этих четырех предположений можно построить как обобщение доказательств, проведенных для алгоритма PRIM в гл. 4; они предлагаются в качестве упражнений.

Пример на рис. 5.5.4 иллюстрирует, что минимальное возможное число ребер, выбранных на шаге I, равно ГМ/2"1 и что в этом случае образуется \ М/2 \ поддеревьев. По тем же причинам очевидно, что если при входе в шаг 3 было сформировано г поддеревьев, то будет выбрано по крайней мере f г/2"] дополнительных ребер при однократном применении шага 3. Кроме того, очевидно, что каждое из этих выбранных ребер уменьшит на 1 число остающихся поддеревьев.



[0] [1] [2] [3] [4] [5] [6] [7] [8] [9] [10] [11] [12] [13] [14] [15] [16] [17] [18] [19] [20] [21] [22] [23] [24] [25] [26] [27] [28] [29] [30] [31] [32] [33] [34] [35] [36] [37] [38] [39] [40] [41] [42] [43] [44] [45] [46] [47] [48] [49] [50] [51] [52] [53] [54] [55] [56] [57] [58] [59] [60] [61] [62] [63] [64] [65] [66] [67] [68] [69] [70] [71] [72] [73] [74] [75] [76] [77] [78] [79] [80] [81] [82] [83] [84] [85] [86] [87] [88] [89] [90] [ 91 ] [92] [93] [94] [95] [96] [97] [98] [99] [100] [101] [102] [103] [104] [105] [106] [107] [108] [109] [110] [111] [112] [113] [114] [115] [116] [117]

0.0012