A parallel algorithm for searching the minimum weight spanning tree on prefractal graph.pdf В работе предлагается описание параллельного алгоритма R поиска остовного де-рева минимального веса (ОДМВ) [1] на предфрактальном графе [2, 3].В основе определения фрактальных графов лежит операция замены вершины за-травкой (ЗВЗ). Термином «затравка» условимся называть какой-либо связный графH = (W, Q). Суть операции ЗВЗ заключается в следующем. В данном графе G = (V, E)у намеченной для замещения вершины V Е V выделяется множество V С V смежныхей вершин. Далее из графа G удаляется вершина V и все инцидентные ей рёбра. За-тем каждая вершина Vj Е V, j = 1, 2, VV , соединяется ребром с одной из вершинзатравки H. Вершины соединяются произвольно (случайным образом) или по опреде-лённому правилу при необходимости.Предфрактальный граф будем обозначать через GL = (VL,EL) , где VL - множе-ство вершин графа, а EL - множество его рёбер. Определим его рекуррентно, по-этапно заменяя каждый раз в построенном на предыдущем этапе l = 1, 2 , . . . , L - 1графе GI = (V, Ej) каждую его вершину затравкой H. На этапе l = 1 предфрак-тальному графу соответствует затравка G1 = H. Об описанном процессе говорят, чтопредфрактальный граф GL порожден затравкой H. Процесс порождения предфрак-тального графа GL по существу есть процесс построения последовательности пред-фрактальных графов Gi, G 2 , . . . , G j , . . . , GL, называемой траекторией. Фрактальныйграф G = (V, E), порожденный затравкой H, определяется бесконечной траекторией.Предфрактальный граф GL условимся называть (n, q, Ь)-графом, если он порожденn-вершинной q-рёберной связной затравкой H.Для предфрактального графа GL рёбра, появившиеся на l-м, l Е {1, 2 , . . . , L } , этапепорождения, будем называть рёбрами ранга l. Новыми рёбрами предфрактальногографа GL назовём рёбра ранга L, а все остальные рёбра назовём старыми.При удалении из предфрактального графа GL всех рёбер рангов l = 1, 2 , . . . , L - rполучим множество { В л : i = 1, 2 , . . . , n L - r } блоков r-го ранга, где i - порядковыйномер блока; r Е {1, 2 , . . . , L - 1}. Термином подграф-затравка z(1) будем называтьблок первого ранга предфрактального графа Gj из траектории. Мощность мно-жества Z(GL) всех подграф-затравок из траектории графа GL равна (nL - 1)/(n - 1).Будем говорить, что предфрактальный граф GL взвешен, если каждому его ребруе(1) Е EL приписано действительное число w(e(1)) Е (91 - ia, 91 - i6), где l - ранг ребра;а > 0 и 9 < а/6.Алгоритм R осуществляет поиск ОДМВ T = (VL,ETT) на взвешенном предфрак-тальном графе GL. Алгоритм использует k процессоров p i , p 2 , . . . ,Pk на многопроцес-сорной вычислительной машинес распределённой памятью. Назначим каждый про-цессор одной из подграф-затравок z(1), l = 1 , . . . , L, s = 1 , . . . , n 1 - i , предфрактальногографа GL, тогда число используемых процессоров равно k = (nL - 1)/(n - 1). Сутьработы алгоритма заключается в следующем. Каждая подграф-затравка z(1) рассмат-ривается как отдельно взятый граф. При этом каждый из k процессоров p^ i = 1 , . . . , k,независимо от других находит ОДМВ Ti на своей подграф-затравке z(1). Поиск ОДМВотдельно взятой подграф-затравки осуществляется алгоритмом Прима. НахождениеОДМВ Ti , T 2 , . . . ,Tk всех подграф-затравок z(1) определяет ОДМВ T предфракталь-ного графа GL. Каждое ребро предфрактального графа имеет свой уникальный но-мер, однозначно определяющий ребро во всей траектории. Таким образом, выделениеОДМВ на подграф-затравке z(1) соответствует выделению множества рёбер на пред-фрактальном графе GL.Кроме принципиальной возможности эффективного распараллеливая задачи о по-иске ОДМВ на предфрактальном графе важен еще и следующий факт.Теорема 1. Вычислительная сложность алгоритма R для предфрактального(n, q, Ь)-графа (GL) с числом вершин |VL| = N равна O(Nn2).Вычислительная сложность алгоритма Прима равна O(N2). Сравнив её с вычис-лительной сложностью алгоритма R, получаем, что при реализации алгоритма R наодном процессоре поиск ОДМВ на предфрактальном графе будет осуществлен быст-рее, чем широко известным алгоритмом Прима.

Скачать электронную версию публикации