Рассмотрим взвешенный предфрактальный [1], (n, L) - граф G = (V,E) и траекторию G1 = (V1,E1), l=1,2,...,L. Пусть имеется k процессов [2] p1,p2,...,pk, где 
и каждый из k процессоров, назначен одной из затравок 
Множество всех затравок Zs (l) всех рангов предфрактального (n, L), графа G = (V,E) обозначим через 
, 
Идея работы параллельного алгоритма Соллина α поиска остовного дерева минимального веса [3] заключается в следующем.
Каждая затравка рассматривается как отдельный подграф, и k процессоров p1, p2,..., pk параллельно и независимо друг от друга находят остовные деревья минимально- го веса (ОДМВ), каждый на своей назначенной затравке Zs(l) . Объединяя полученные результаты, т.е. выделенные ОДМВ, получим ОДМВ предфрактального (n,L)-графа G=(V, Е). Обосно- ванием работы алгоритма Соллина α являются следующие теоремы:
Теорема 1. Параллельный алгоритм Соллина α строит на предфрактальном (n,L)-графе G=(V, Е), остовное дерево минимального веса Т=(V, ЕS).
Теорема 2. Вычислительная сложность алгоритма Соллина для связного взвешенного графа G=(V,E), |V|=n, |E|=m, где имеется n процессоров (компьютеров) p1,p2,…pn, каждый из которых назначен одной из вершин v1,v2,…,vn графа G=(V, E), равна Zs(l) О(n2 log2 n).
Литература
- Кочкаров А.М. Распознавание фрактальных графов. Алгоритмический подход. Нижний Архыз: САО РАН.-1998.
- Воеводин В.В. Математические модели и методы в параллельных процессах.М.: Наука, 1986.
- Гудман С., Хидетниеми С. Введение в разработку и анализ алгоритмов.-М.: Мир, 1981