Уnr = n-0+1. Тогда паросочетание М графа G=(V, E), полученное параллельным

алгоритмом а является максимальным.

Доказательство. Согласно конструкции параллельного алгоритма а, в результате работы части а1 исходный граф G=(V, E) разбивается на 0 связных подграфов Gr=(Vr, Er), r=1, 2, 0. На вход каждого этапа а2 , te {1, 2, 0} подается граф

G0-t+1 = V0-t+1,E0-t+1 ) На каждом этапе аf2 , t=1, 2, 0, части а2 работает алгоритм Габова [2], который находит максимальное паросочетание М0-ш.

Паросочетание М графа G, полученное в части а3 алгоритма а равно объединению всех максимальных паросочетаний М0-ш, полученных на этапах а2 , t=1, 2, ..., 0.

Предположим, что М - не является максимальным паросочетанием графа G, т. е. в G существует другое паросочетание M c M >M. Рассмотрим ребра, входящие в МФ M, где Ф - знак симметрической разности. Эти ребра образуют подграф G с G графа G. Поскольку никакие два ребра не могут быть инцидентны одной и той же вершине в паросочетании М, то подграф G=(V, МФМ) имеет специальную структуру - все его вершины имеют степень 2 и меньше. Если степень вершины в G равна 2, то одно из инцидентных ей ребер входит в М, а другое - в M . Поэтому компоненты в G должны быть либо цепями, либо циклами четной длины с чередованием ребер из М и из M . Поскольку M >M, то среди этих компонентов необходимо есть цепь нечетной длины, начинающаяся и оканчивающаяся ребрами M , которая является увеличивающей цепью. Однако из конструкции алгоритма а следует, что среди компонентов графа G нет цепей

нечетной длины, начинающихся и оканчивающихся ребрами M . Получили противоречие, следовательно, М - максимальное паросочетание графа G. Таким образом теорема 1 доказана. Докажем теперь, что справедлива

Теорема 2. Пусть задан граф G=(V, E), V=n, E=m, состоящий из 0 компонент

связности Gr=(Vr, Er), r=1, 2, 0 и 0-1 точек сочленения, Vr=nr, Er=mr, уmr = m,

Уnr = n-0 +1, 0>2. Тогда высота Н(а) параллельного алгоритма а нахождения

максимального паросочетания в графе G равна 0+2, т. е. Н(а)=0+2.

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

связности Gr=(Vr, Er), r=1, 2, 0 и 0-1 точек сочленения, Vr=nr, Er=mr, Vmr

0 Г п 1

Vnr = п-0 +1, n*= min nr, п* = max nr, n* > l/nnl, n* < - , 2 < 0 <

, 1<r<0 1<r <0 2

n Inn

Тогда ширина

S(а) параллельного алгоритма а нахождения максимального паросочетания графа G

f n 31

удовлетворяет соотношению S (а) = O - .

Доказательство. Согласно конструкции параллельного алгоритма а, ярус 1 представляет собой группу операций 2-расщепления точек сочленения графа G. Поэтому трудоемкость такого яруса составляет О(0) элементарных операций. Каждый из ярусов 2, 3, ., 0+1 представляет собой группу операций алгоритма Габова [2] выделения максимального паросочетания графа Gr=(Vr, Er), re {1, 2, 0}, поэтому трудоемкость каждого такого яруса составляет o(n3) элементарных операций. Ярус 0+2 представляет собой группу операций объединения паросочетаний Mr, re {1, 2, 0} полученных в части а2. Поэтому трудоемкость такого яруса составляет О(0) элементарных операций. Для нумерации ребер графа Gr=(Vr, Er) потребуется ООпчГ) элементарных операций[5]. Используя теперь определение ширины параллельного алгоритма а и условия теоремы 3, имеем

S(а) = max 0(0) O - , O(0), O -

n3 1 J nd 1 J, n3

O

Таким образом, теорема 3 доказана.

условий алгоритма, либо от результатов выполнения операций, находящихся в предыдущих группах:

1) операции расщепления точек сочленения графа G=(V, E);

2) операции алгоритма Габова [2] нахождения максимального паросочетания в каждом графе Gr=(Vr, Er), re {1, 2, 0};

3) операции объединения паросочетаний Mt графов Gt, te {1, 2, ..., 0} полученных соответственно на этапах а2 с помощью операции замыкания вершин vr,re {1, 2, 0-1}.

Поскольку, согласно конструкции параллельного алгоритма а, каждая из групп 1), 3) выполняется 1 раз, а группа операций 2) - 0-раз, то число ярусов параллельного алгоритма а равно 0+2. Отсюда и из определения высоты параллельного алгоритма а следует, что Н(а)=0+2, где 0>2. Таким образом, теорема 2 доказана.

Теорема 3. Пусть задан граф G=(V, E), V=n, E=m, состоящий из 0 компонент

--n-0 +1, nr <

n* = min nr, n* = max nr, 2 < 0 <

1<r<0 1<r <0

n ln n

> /nn], n *

< -. Тогда 2

ускорение А(а) параллельного алгоритма а нахождения максимального паросочетания графа G удовлетворяет неравенству

А(а)=О(0+2).

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

параллельного алгоритма а, а через Ца) - число операций последовательной реализации параллельного алгоритма а. Из определения ускорения параллельного алгоритма следует,

что

Л(а)--

np (а)

Принимая во внимание равенство (а^Б^) и соотношение (1), получим

,(а)= O

Г

где 2 < 0<

ln n

Величина n(а) согласно определению удовлетворяет равенству

Г 3 n)= O -т -(0 + 2).

103)

Подставляя теперь (3), (4) в правую часть равенства (2), получим А(а)=О(0+2). Таким образом, теорема 4 доказана. Из теорем 3, 4 вытекает

Следствие 2. Пусть выполняются условия теоремы 3. Тогда параллельный

алгоритм а находит максимальное паросочетание графа G за время O

элементарных

Из теорем 2, 3 вытекает

Следствие 1. Пусть выполняются условия теоремы 3. Тогда высота Н(а)параллельного алгоритма а выделения максимального паросочетания графа G удовлетворяет неравенству

4 < H (а)< - + 2. lnn

Теорема 4. Пусть задан граф G=(V, E), V=n, E=m, состоящий из 0 компонент связности Gr=(Vr, Er), r=1, 2, 0 и 0-1 точек сочленения, Vr=nr, Er=mr, уmr

Литература.

1. Ловас Л., Пламмер М. Прикладные задачи теории графов. Теория паросочетаний в математике, физике, химии.-М.:Мир, 1988.-653с.

2. H. N. Gabow. An Efficient Implementation of Edmons Algorithm for Maximum Matching of Graphs. J. ASM, vol. 23, 221-234 (1976).

3. M. I. Balinski. Labeling to Obtain a Maximum Matching in Combinatorial Mathematics and Ins Applications (R. C. Bose and T. A. Dowling, Eds), Univ., North Carolina Press Chappel Hill, N. C., 1967, p. p. 585-602.

4. Воеводин В. В. Математические модели и методы в параллельных вычислительных системах. M.: Наука, 1986. - 296 с.

5. Емеличев В. А. и др. Лекции по теории графов. М.: Наука, 1990. - 384 с.

6. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984. - 455 с.

операций, используя параллельную вычислительную систему, состоящую из 0+2 процессоров.