Параллельные алгоритмы решения некоторых экстремальных задач на графах

Шунгаров Х. Д. (hamidsh@rambler.ru )

Карачаево-Черкесский Государственный Университет

1. Введение.

Задача нахождения остовного дерева минимального веса (ОДМВ) графа G возникает при проектировании линий электропередач, трубопроводов, дорог и т. п., когда требуется заданные центры соединить некоторой системой каналов связи так, что любые два центра были связаны непосредственно соединяющими их каналами, либо через другие центры и каналы, и чтобы общая длина (стоимость) каналов связи была минимальной.

Известно [1, 2, 3, 4], что для задач нахождения остовного дерева минимального веса и леса максимального веса (ЛМВ) графа существуют эффективные алгоритмы. В [5] представлен параллельный алгоритм

нахождения ОДМВ графа, ускорение которого составляет Хо п) В

настоящей работе для нахождения ОДМВ и ЛМВ в классе связных взвешенных графов предлагаются параллельные алгоритмы, ускорение каждого из которых составляет О(п) .

Пусть имеется конвейерная параллельная вычислительная система, представляющая собой последовательность из 2 процессоров, каждый из которых осуществляет лишь один шаг задания, передавая результаты следующему процессору, который делает очередной шаг. Таким образом, для вычисления результата данные передаются от одного процессора к другому. Предположим также, что имеется некоторый алгоритм а, операции которого разбиты на группы, упорядоченные так, что каждая операция любой группы зависит либо от начальных условий алгоритма, либо от результатов операций, находящихся в предыдущих группах. Представление алгоритма в подобном

2. Постановка задачи.

Пусть задан неориентированный связный граф G=(V, E), V={v1, v2, vn}, E={e}, e=(vi, Vj), Всякому ребру eeE приписан вес w(e)=w(vi, Vj)>0. Такой граф будем называть взвешенным. Обозначим через x=(V, Ex) - суграф[7], который является остовным деревом графа G, Ex<E. Множество всех таких остовных деревьев обозначим через X={x}. На множестве Х определим целевую функцию (ЦФ)

F(x) = у w(e) -- min. (1)

eeEx

Требуется найти такой элемент х0еХ, на котором ЦФ F(x) (1) принимает минимальное значение, т. е.

F (x0 )= min F (x). (2)

xe X

Множество Х называется множеством допустимых решений, а элемент х0, удовлетворяющий равенству (2), называется оптимальным решением или

виде называется параллельной формой алгоритма или параллельным алгоритмом [6].

Каждая группа операций называется ярусом параллельного алгоритма, число групп - высотой, а максимальное число операций в ярусе - шириной параллельного алгоритма [6]. Высоту (ширину) параллельного алгоритма а обозначим через Н(а) (S(a)).

Все недостающие определения понятий, относящихся к теории параллельных алгоритмов можно найти в [5, 6]; в [7] представлены определения понятий, относящихся к теории графов.

Ускорением A(a) называется величина, показывающая, во сколько раз быстрее конкретная задача может быть решена при помощи параллельного алгоритма по сравнению с последовательной реализацией такого алгоритма[6]. Проблема конструирования параллельных алгоритмов для задач на графах является актуальной и практически важной и сводится к задаче разбиения этого графа на подграфы.

оптимумом. Сформулированная задача называется задачей нахождения ОДМВ на графе G, для решения которой предлагается параллельный алгоритм а., основанный на идее алгоритма Прима [7].

3. Описание параллельного алгоритма а.

Предположим, что граф G=(V, E) задан матрицей весов W(G)=W. У этой матрицы wij=w(vi, Vj), если (vi, Vj)eE и Wy=0, если (vi, Vj)E . Обозначим через N (vj)- список вершин, смежных вершине v;, i ф j, i,j е {1,2,..., n}; VT, ET -

множества вершин и ребер строящегося фрагмента ОДМВ графа G. В процессе работы параллельного алгоритма а, описанного ниже, с каждой вершиной v*. е N(v;) связываются две метки а ((v*)) и p(v* ). Метка а(у*)

является минимальным весом ребра (v;, v*) , где v*eN (v.), т.е. aiv*j)= min a)(vi,vj), а p(v*) - имя второй вершины этого ребра, т.е. p(v*)= v;.

vj eN (vt)

Параллельный алгоритм а состоит из этапов at, перенумерованных индексом t=1, 2, ...,п-1.Этап а1 начинается с того, что фиксируется некоторая вершина v[eV и определяются множества VT= {vi}, ET=0. Вершина v[eV вошла

во фрагмент строящегося ОДМВ графа G. На вход этапа а^ подается список

N (vi) и каждой вершине ve N(vi) приписываются метки а(у) = a(vi, v), р(у)=vi. Затем все метки a(v), v е N(yi) сравниваются между собой и выбирается метка а^р) = min а(> ), имеющая минимальное значение; p(vp )=vi. Ребро ( vp,vi)

veN (v,)

присоединяется к фрагменту строящегося ОДМВ графа G, а множества VT, ET изменяются следующим образом: VT= \vi,vp }, ET = {vp,v, ) }. После чего метки

а(ур), p(vp) вершины vp удаляются .

На вход этапа а2 подается список N(vp), метки всех вершин vеn(v,)\VT и

множества VT, ET. В списке N(vp) удаляется вершина v, . Каждой вершине

v <£ (n(ур )\ {vi })n N(yi) приписываются метки a(y) = a(yp,v) fl(y) = vp . Для каждой

вершины v e(N (yp) \ {yi })n N (yi) метки изменяются следующим образом. Если для

вершины ve (n(yp)\{yi}) выполняется неравенство a(y)<a(yp,v), то метки

a(y), e(v) вершины v не меняются. Если для вершины v e (n(vp )\ {vi})

выполняется неравенство a(v)>co(vp,v) ,то a(v) = co(vp,v) p(v) = vp . Затем все метки

сравниваются между собой и выбирается

меткаа(уу)= min а(),гдеV2 = N(vi)uN(vp)\{vi}, p(vy) = vz , z = iилиz = p Ребро

veV2\VT

(vz, vy) присоединяется к фрагменту строящегося ОДМВ графа G , а множества

VT, ET изменяются следующим образом VT= {vi,vp,vy}, ET = {vp,vi ),(vy,vz)}.

После чего метки a(vy), fl(vy) вершины vy удаляются .

Пусть осуществлено k-1 этапов att e{1,2,..., k -1} параллельного алгоритма a.

Множество VT содержит k-1 вершин, а множество ET -(k-2) ребер строящегося ОДМВ графа G. Предположим также, что в результате работы первых k-1 этапов at t e{1,2,...,k -1} получено множество меток и (vs,vm) - последнее ребро

минимального веса, присоединенное к фрагменту строящегося ОДМВ графа

G, где vs e VT .

На вход этапа ak k e {1,2,...,n -1} подается список N(vm) , множества VT, ET и множество меток a(v)veVk-1 \VT , полученных в результате работы k-1 этапов att e{1,2,...,k-1}, где Vk-1- множество всех вершин, имеющих метки. В списке N(vm) удаляется вершина vs. Если N(vm )ф 0, т.е. не все вершины списка N(vm) помечены, то каждой вершине vu(n(vm)\{vs})nVk-1 \VT приписываются метки a(v) = co(vm,v), fl(v) = vm . Для каждой

вершины v e(N (vm )\{vs })n Vk-1\VT метки изменяются следующим образом. Если a(v)<a(vm,v), то метки a(v)p(v) вершины v не меняются. Если же a(v)>a(vm,v) ,то a(v) = co(ym,v), p(v) = vm . Множество всех вершин, имеющих метки на этапе ak, обозначим через Vk. Затем все метки сравниваются между собой и

Электронный журнал ИССЛЕДОВАНО В РОССИИ 1 8 2 5 http: zhurnal.ape.relarn.ru/articles/2003/150.pdf выбирается метка а(уг )= min а(у), имеющая минимальное значение, для

veV2\VT

которой p(vr) = vx ,vxeVT . Ребро (vr,vx) присоединяется к фрагменту

строящегося ОДМВ графа G , а множества VT, ET изменяются следующим образом VT= VTJ {vr }, ET =ET J {vr,vx}. Затем метки а(уг),p(vr) вершины vr

удаляются . Если N (vm )= 0, т.е. не все вершины списка N (vm) помечены, то метки а(>\ v е Vk 1 \ VT сравниваются между собой и выбирается метка а(уд )= min а((), имеющая минимальное значение, для которой

veVt\VT

P(vq) = vf , vf VT . Ребро (vq, vf) присоединяется к фрагменту строящегося

ОДМВ графа G , а множества VT, ET изменяются следующим образом: VT= VT (J {vq }, ET =ET j {vq, vf )}. Затем метки а\уч), p(vq) вершины vq

удаляются . Параллельный алгоритм а заканчивает свою работу по завершению этапа ап 1 , т.е. когда VT =V . 4. Анализ и обоснование алгоритма а.

При анализе всякого алгоритма особое место занимает оценка его трудоемкости [6]. Под трудоемкостью алгоритма будем понимать время выполнения соответствующей программы на ЭВМ. Трудоемкостью алгоритма называется функция f, ставящая в соответствие каждому натуральному числу n время работы f(n) алгоритма в худшем случае на входах длины n[6].

При анализе и обосновании алгоритмов будем использовать О-символику. Будем говорить, что неотрицательная функция f(n) не превосходит по порядку функцию g(n), если существует такая константа с, что f(n)<cg(n) для всех n>0 и при этом будем писать f(n)=O(g(n)). Иногда вместо трудоемкость алгоритма есть O(g(n)) будем говорить алгоритм решает задачу за время O(g(n)) [7].

Пусть T = {(VbT),(V2,T2),...,(Vk,Ek)} - остовный лес взвешенного графа G , V; и E; - множества вершин и ребер i -ой компоненты леса T. Параллельный алгоритм а опирается на следующую известную теорему [7].

Теорема 1. Пусть ребро (и, v) имеет минимальный вес среди всех ребер, у

которых ровно одна концевая вершина содержится в VT1. Тогда среди

остовных деревьев графа G, содержащихTj[ {(и,v)}, найдется такой, вес

которого не более веса любого остовного дерева, содержащего T. Докажем теперь, что справедлива

Теорема 2. Пусть задан связный взвешенный граф G=(V, E), V=(vi, v2, vn}, E={e}, e=(vi, vj), i,j=1, 2, n, iij. Тогда построенный параллельным алгоритмом а граф T = (VT, ET), представляет собой ОДМВ графа G.

Доказательство. Сначала докажем, что граф T = (VT, ET), полученный в результате работы параллельного алгоритма а , является деревом. Поскольку согласно конструкции параллельного алгоритма а, на каждом этапе att e {1,2,...,n -1} к ET добавляется ребро, одна концевая вершина которого

принадлежит VT, а другая - нет, то граф T = (VT, ET) на каждом этапе at,te {1,2,...,n -1}является деревом. После завершения работы параллельного

алгоритма a это дерево T будет остовным деревом графа G, поскольку параллельный алгоритм a заканчивает свою работу только если VT=V.

Докажем теперь, что построенное параллельным алгоритмом a остовное дерево T= (VT, ET) является ОДМВ графа G. Для этого достаточно доказать, что после выполнения этапа ak,k e {1,2,...,n -1} построенный граф Tk = (Tk, ET k) содержится в некотором ОДМВ графа G. Докажем индукцией по

k. При k=1 утверждение о том, что после выполнения этапа a построенный граф T =(VT1, ET1 ) содержится в некотором ОДМВ графа G непосредственно следует из теоремы 1. Предположим, что это утверждение справедливо для некоторого k>1, т.е. граф Tk, построенный в результате работы k этапов att e {1,2,..., k} содержится в некотором ОДМВ графа G. Учитывая правило

выбора ребра e для присоединения к Tk на этапе ak+1, k e {1,2,..., n - 2} применим теорему 1.Тогда получим, что граф Tk+1 = Tk ue, построенный в результате

выполнения этапа ak+\к е {1,2,...,п 2} также содержится в некотором ОДМВ

графа G. Таким образом, теорема 2 доказана.

Теорема 3. Пусть задан связный взвешенный граф G=(V, E), V={v1, v2, vn}, E={e}, e=(vi, vj), i,j=1, 2, n, iij. Тогда высота параллельного алгоритма а удовлетворяет равенству:

H(a1)=n-1.

Доказательство. Согласно конструкции параллельный алгоритм а состоит из п 1 этапов,. каждый из которых представляет ярус параллельного алгоритма а . Отсюда и из определения высоты параллельного алгоритма следует, что H(a)=n-1. Теорема 3 доказана.

Теорема 4. Пусть задан связный взвешенный граф G=(V, E), V={v1, v2, ., vn}, E={e}, e=(v;, vj), ij=1, 2, n, iij.Тогда ширина параллельного алгоритма а определяется соотношением:

S (a)= O(n). (3)

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

1) присваивание и изменение меток;

2) нахождение вершины, ближайшей к фрагменту строящегося ОДМВ графа G и присоединение ребра минимального веса;

3) удаление вершины из списка вершин.

Каждая группа операций 1)-3) требует времени не более O(n), поэтому

S (а) = о(п). Таким образом, теорема 4 доказана.

Теорема 5. Пусть задан связный взвешенный граф G=(V, E), V={v1, v2, vn}, E={e}, e=(v;, vj), i,j=1, 2, n, iij. Тогда ускорение параллельного алгоритма а удовлетворяет соотношению: A(a)=O(n).

Доказательство. Обозначим через Р1 (а) - число операций параллельного

алгоритма а1, а через Р2 (а)- число операций последовательной реализации параллельного алгоритма а. Величина Р1 (а) является шириной параллельного алгоритма а, поэтому согласно (4) имеем:

P (а) = O(n). (5)

Величина P2 (а) составляет o(n2) элементарный операций, т. е.

P2(а ) = 0(г2). (6)

Из определения ускорения параллельного алгоритма а следует, что

4*)=P2 (а)/р (а). (7)

Подставляя теперь (5) и (6) в правую часть (7), получим A(ai)=O(n).

Таким образом, теорема 5 доказана. Из теорем 3, 4 вытекает Следствие 1. Пусть выполняются условия теоремы 4. Тогда параллельный алгоритм а находит ОДМВ графа G за время o(n) элементарных операций, используя параллельную вычислительную систему, состоящую из n-1 процессоров.

4.Задача нахождения леса максимального веса (ЛМВ).

Пусть дан граф G=(V, E) и вес w(e)=wij>0 для каждого ребра ееЕ. Требуется найти лес - ациклический подграф графа G, - имеющий максимальный общий вес. Такой граф G будем называть графом G с весами w. Введем функцию расстояния для Е графа G: dij=W-wij, где w = maxwtj , тогда такой граф G будем

называть графом G с расстоянием d [4]. Известна [4] следующая

Теорема 6. Пусть задан связный взвешенный граф G=(V, E), V={v1, v2, vn}, E={e}, e=(vu vj), ij=1, 2, n, Щ. Остовное дерево минимального веса в графе G с расстоянием d совпадает с лесом максимального веса в графе G с весами w .

Из теоремы 6 следует, что параллельный алгоритм а можно применить к задаче нахождения ЛМВ графа G, изменив вес каждого ребра ееЕ следующим образом: dij=W-wij, w = maxw(e). Таким образом, имеет место следующая

Теорема 7. Пусть задан связный граф G=(V, E), V={v1, v2, vn}, E={e}, e=(vi, vj), ij=1, 2, n, iij. Всякое ребро ееЕ взвешено числом wij=w(e)>0. Введем функцию расстояния dj=W-Wj, w = гшх w(e). Тогда

1) решение х0, полученное параллельным алгоритмом а, представляет собой ЛМВ графа G;

2) высота Н(а) параллельного алгоритма а нахождения ЛМВ графа G удовлетворяет равенству н(а ) = п 1;

3) ширина S(q) параллельного алгоритма а нахождения ЛМВ графа G удовлетворяет соотношению s(а) = o(n);

4) ускорение параллельного алгоритма а нахождения ЛМВ графа G удовлетворяет равенству A(q)=0(n).

Работу параллельного алгоритма а рассмотрим на графе G, изображенном на рис.1.

Рис.1. Граф G = (v, E), V = n, n = 19 .Ребра, вошедшие в ОДМВ выделены.

Ad.1. Graph G = (v, E), I V 1 = n,n = 19.Spanning Tree of a Minimal Weight

entered Ribs are marked.

Параллельный алгоритм а состоит из © = 18 этапов.

Этап а1. На вход этапа а1 подается список N(v1). Каждой вершине v е N(v1)

приписываются метки: а

(v2 ) = 1p(v2 ) = v1

a(v3 ) = 2p(v3 ) = v1 .

Этап a2 . На вход этапа a2 подается список N (v2), множества VT,ET

и

метки a(v), v е N(v1) . Затем вершина v1 удаляется из списка N(v2). Каждой вершине v е N(v2 )\ {v1} приписываются метки:

a(v6 )= 5 e(v6 ) = v2 a(v3 ) = 3 e(v3 ) = v2 a(v5 ) = 4 e(v5 ) = v2.

Вершина v3eN (v1 )n N (v2) \ {v1}, поэтому метки вершины v3 изменяются a(v3 )= 2 e(v3 ) = v1. Метки a(v),v е N(v1) сравниваются между собой и выбирается метка a(v2 ) = 1р(у2 ) = v1. Ребро (v1, v3) присоединяется к фрагменту строящегося ОДМВ графа G. Множества VT, ET изменяются следующим образом: VT= {v1,v2, , ET= {(v1, v2), (v1, v3)}. После чего метки a(v3), e(v3) удаляются. Аналогичным образом работают остальные этапы.

Этап а3. На вход этапа а3 подается список N(v3), множества VT,ET и метки a(v), v е N(v2). Затем вершина v3 удаляется из списка N(v3). Каждой вершине v е N(v3)\ приписываются метки:

a(v6 )= 1 e(v6 ) = v3 a(v8 ) = 1 e(v8 ) = v3 a(v4 ) = 2 e(v4 ) = v3 a(v5 )= 4 e(v5 ) = v2 VT= {vl, v2, v6 } ,ET= {(v1, v2 ), (v1, v3 ) (v3, v6)}. Этап a4 : N(v6 ) : a(v10 ) = 1 e(v10 ) = v6

a(v8 ) = 1 e(v8 ) = v3 a(v4 ) = 2 e(v4 ) = v3 a(v5 ) = 4 e(v5 ) = v2

Метки a(v), v е N (vi) сравниваются между собой и выбирается метка a(v2 ) = ip(v2 ) = v1. Ребро (v1,v2) присоединяется к фрагменту строящегося ОДМВ графа G. Множества VT, ET имеют вид: VT= {v1, v2}, ET= {(v1, v2)}. После чего метки a(v1 ),a(v2) удаляются