Параллельный алгоритм нахождения максимального

паросочетания в графе

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

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

1. Введение

Задача нахождения максимальных паросочетаний в графе имеет множество приложений[1]. Известно [2, 3], что для решения задачи о паросочетании имеются эффективные алгоритмы. В настоящей работе для решения задачи нахождения максимального паросочетания в графе предлагается параллельный алгоритм а, вместе с обоснованием его эффективности.

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

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

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

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

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

Пусть задан связный неориентированный граф G=(V, E), с n=V вершинами и

E=m ребрами, состоящий из 0 компонент связности Gt=(Vt, E, t=1, 2, 0 и 0-1 точек

сочленения, Vt=nt, Et=mt, mt = m, nt = n-0 +1. Напомним, что паросочетанием графа

t=1 t=1

G=(V, E) называется подграф x=(Vx, Ex), порожденный на множестве попарно-несмежных ребер Ехс Е, VxcV. Паросочетание х0 называется максимальным, если число ребер в нем наибольшее среди всех паросочетаний графа G. Задача о паросочетании состоит в нахождении максимального паросочетания х0 графа G.

В настоящей работе для решения задачи о паросочетании предлагается

С 3 А

параллельный алгоритм а, трудоемкость которого составляет O

0 з

V0 J

операций, где

параметр 0>2 удовлетворяет неравенству 2 <0<

Уменьшение времени работы

предлагаемого алгоритма получено за счет его представления в параллельной форме и при том условии, что задача о паросочетании будет решаться на параллельной

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

Актуальным и практически важным является нахождение верхних и нижних оценок высот параллельных алгоритмов для решения классов задач.

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

- расщепление задачи на независимые подзадачи;

- выделение в задаче потока независимых однотипных задач;

- применение принципа разделяй и властвуй с рекурсивным расщеплением задачи на две или несколько задач[4].

Рис. 1. Граф G=(V, E) и его компоненты связности G1, G2, ..., G0.

В дальнейшем нам понадобится следующее определение. Расщепление точки сочленения v графа G=(V, E), на k вершин такое, что получаются k реберно-непересекающихся подграфов Gk=(Vk, Ek), k=1, 2, 0, будем называть k-расщеплением точки сочленения.

12 3 1

Параллельный алгоритм а состоит из трех частей: а , а , а . Часть а состоит из а1г шагов, перенумерованных индексом r=1, 2, ..., 0-1. На каждом шаге а1г фиксируется

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

В дальнейшем нам понадобятся следующие определения [5]. Вершина ve V называется насыщенной паросочетанием М графа G, если она является концевой вершиной некоторого ребра eeM. Чередующейся цепью Р в графе G называется цепь, ребра которой поочередно входят в М или Е\М. Пусть Р - чередующаяся цепь между двумя ненасыщенными вершинами в паросочетании М. Тогда симметрическая разность двух множеств ребер МФР является паросочетанием с числом ребер на единицу больше, чем в паросочетании М. При этом цепь Р называется увеличивающейся цепью по отношению к М.

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

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

Et), t=1, 2, 0 и 0-1 точек сочленения, Vt=nt, Et=mt, уmt = m, уnt = n-0 +1, задан

t=1 t=1

списками смежности Nv, где Nv - список вершин, смежных вершине ve V.

точка сочленения vr графа Gr и эта вершина vr 2-расщепляется, re {1, 2, 0-1}. В результате работы части а1 исходный граф G=(V, E) разбивается на 0 подграфов Gt=(Vt, Et), te {1, 2, 0}.

Часть а алгоритма а состоит из этапов а2, перенумерованных индексом t=1, 2 0. На вход каждого из этапов а2, te {1, 2 0} соответственно подается граф

G0-t+1 = +1,E0-t+1 где V0-t+1 = n0-t+l, E0-t+1 = m0-t+1- Каждый этап а^ te {1, 2, 0} начинает свою работу с нумерации ребер графа G0-t+1 числами n0-t+1 + 2, n0-t+1 + 4, n0-t+1 + 2m0-t+1. Номер ребра (u, v) будем обозначать через N(u, v). Множество E0-t+1 ребер графа G0-t+1 хранятся в массиве END, элементы которого пронумерованы числами n0-t+1 +1, n0-t+1 + 2, n0-t+1 + 2m0-t+1. На каждом этапе а2, te {1, 2, 0} работает алгоритм Габова [2], который находит максимальное паросочетание M0-t+1 графа G0-t+1 =(v0-t+1,E0-t+1). Каждое паросочетание Mr, r=1, 2, 0, хранится в массиве МАТ,

который имеет по одному элементу для каждой вершины графа Gr. Ребро (v, w)eEr входит в паросочетание Mr, если MАТ(v)=w и МАТ^).

Вершина ve Vr графа Gr, re {1, 2, ., 0} называется внешней по отношению к фиксированной ненасыщенной вершине w тогда и только тогда, когда в этом графе существует чередующаяся цепь четной длины от w к v. Эта цепь P(v)=(v, v1, v2, ..., w) начинается с ребра (v, v1), вошедшего в паросочетание Mr графа Gr, re {1, 2, 0}. Если на каком-либо шаге этапа а2, te {1, 2, 0} рассматривается ребро, соединяющее внешнюю вершину w с ненасыщенной вершиной w/w, то при этом выделяется увеличивающаяся цепь вида w *P(v) = (wv,v1,...,w), где * - обозначение конкатенации. Если такое ребро в графе G0-t+1 на этапе а2, te {1, 2, 0} не обнаружено, то вершина w/ не войдет ни в одну увеличивающую цепь.

На каждом этапе а2, te {1, 2, 0} используется массив LABEL, состоящий из

n0-t+1 = F0-t+1 элементов такой, что каждой вершине графа G0-t+1 соответствует один

элемент. При этом элемент массива, соответствующий внешней вершине v, используется для определения увеличивающей цепи P(v). Элемент массива LABEL интерпретируется как начальная метка, или как метка вершины, или как метка ребра. Начальная вершина v0 имеет начальную метку. Увеличивающая цепь при этом P(v0)=v0.

Каждый этап а2, te {1, 2, 0} начинается с того, в графе G0-t+1 в качестве

начальной вершины выбирается точка сочленения v0-teV0-t+1, для которой LABEL(v0-t)=0.

Если LABEL(v)=i, где 1<i<nt, nt = Vt , t=1, 2, 0, то говорят, что вершина v

имеет метку вершины. В этом случае v является внешней вершиной и элемент LABEL(v) равен номеру другой внешней вершины. Цепь P(v)= (v, MAT (V ))* p(LABEL(v)).

Если LABEL(v)= mt+2i, где 1< i <nt, mt = Et , te {1, 2, 0}, то говорят, что

вершина v имеет метку ребра. Если v - внешняя вершина и LABEL(v) содержит номер ребра, соединяющего две внешние вершины, то LABEL(v)=N(x, y). Метка ребра N(x, y) вершины v указывает, что существует чередующаяся цепь четной длины из v в начальную вершину u, которая проходит через ребро (x, y). Пусть v принадлежит цепи Р(х), а P(x, v)-часть цепи Р(х) из x в v, тогда цепь P(v) = revP(x, v)* p(y), где revP(x, v)-обращение цепи из х в v.

Если LABEL(v)<0, то вершина v не является внешней. В начале каждого этапа а2, te {1, 2, 0} полагаем LABEL(v)= -1 для всех вершин ve V0-t+1 графа G0-t+1.

На каждом этапе а2, te {1, 2, 0} алгоритма а используются массивы FIRST и

OUTER. Если v - внешняя вершина, то FIRST(v) - первая не внешняя вершина в цепи P(v); если v - не внешняя вершина, то FIRST(v)=0. Массив OUTER используется для хранения внешних вершин, встречающихся при поиске увеличивающей цепи. Граф поиска растет во внешних вершинах в порядке их появления. В этих внешних вершинах графа G0-t+1, te {1, 2, 0} на этапе а2 производится поиск в ширину.

Каждый этап а2, te {1, 2, 0} части а2 алгоритма а представляет собой алгоритм Габова [2] и состоит из трех процедур: PROC-EDMONS, PROC-LABEL, PROC-REMATCH. Процедура PROC-EDMONS является главной. На каждом этапе а2, te {1,2,.,0} эта процедура начинает поиск увеличивающей цепи из каждой ненасыщенной вершины графа G0-t+1 , просматривая его ребра с целью расширить паросочетание и приписать метки. При построении увеличивающей цепи на каждом этапе а2, te {1, 2, 0} вызывается процедура PROC-REMATCH, которая в графе G0-t+1 находит новое паросочетание, на одно ребро большее текущего паросочетания.

Напомним [5, 6], что цветком называется замкнутая чередующаяся цепь нечетной длины.

Если на каком-либо этапе а2, te {1, 2, 0} при рассмотрении некоторого ребра (v,u)e E0-t+1 графа G0-t+1 образуется цветок , то вызывается процедура PROC-LABEL. В

этом случае вершины v и u являются внешними. Процедура PROC-LABEL выполняет следующие операции:

1) вводится переменная JOIN, значением которой является первая не внешняя вершина, которая принадлежит как Р^) так и Р(д);

2) все не внешние вершины, предшествующие JOIN в Р^) или Р(ц) становятся внешними и помечаются меткой ребра N(v, u); эта метка указывает, что к каждой из этих вершин существует чередующаяся цепь четной длины из начальной вершины, который проходит через ребро (v, u);

3) после этого JOIN - первая не внешняя вершина как в Р^) так и в Р(д), поэтому элементы массива FIRST, которые соответствуют вершинам, предшествующим JOIN в Р^) или Р(д), полагаются равными JOIN.

Этап а2, te {1, 2, 0} заканчивает свою работу, как только не окажется

увеличивающей цепи по отношению к текущему паросочетанию графа

G0-t+1 =(v0-t+1,E0-t+1). Каждый следующий этап а2+1, te {1, 2, 0-1} начинает свою

работу с того, что фиксируется точка сочленения v0-teV0-t графа G0-t = (v0-t, E0-t). Если эта вершина v0-t оказалась насыщенной паросочетанием M 0-t+1 графа G0-t+1 , полученным на этапе а2, то v0-t считается насыщенной в графе G0-t, te {1, 2, ..., 0} на этапе а2+1.

Часть а3 параллельного алгоритма а состоит в объединении паросочетаний М0, М0-1, ..., М1, графов G0, G0-1, ..., G1 соответственно полученных на этапах а2, а2, ..., а0

с помощью операции замыкания вершин vr, re {1, 2, ., 0-1} и получении максимального паросочетания M исходного графа G.

Работу параллельного алгоритма а покажем на графе G, изображенном на рис. 2. Граф G состоит из 0=2 компонент связности G1 и G2; v=4 - точка сочленения. На вход части а1 подается граф G=(V, E) и точка сочленения v=4 2-расщепляется. На вход этапа а12 части а2 подается граф G2 (рис 3.).

1 13

Рис. 3. Работа этапа а12 части а2. Ребра паросочетания M2 графа G2 выделены жирными линиями.

Таблица 1.

Рис. 4. Работа этапа а 2.

Таблица 2.

Зафиксируем вершину v=2, которая имеет метку ребра N(3, 4). Определим цепь Р(2): p(2) = revP(3,2)* p(4). Вершина v=4 имеет метку вершины, поэтому P(4) = (4, MAT (4))* P(LABEL(4)) = (4,13)* p(l) = (4,13,l). Следовательно, p(2) = rev(3,2)* p(4) = (2,3)* * (4,13,l) = (2,3,4,13,l)= ((2,3); (4,13)l). По отношению к выделенному паросочетанию нет увеличивающей цепи, поэтому полученное паросочетание является максимальным.

Часть а3 алгоритма а состоит в объединении максимальных паросочетаний, полученных на этапах а2 и а2 с помощью операции замыкания в вершине v=4. Это будет

Зафиксируем вершину v=5, которая имеет реберную метку N(9, 8). Поэтому для определения цепи Р(5) нам потребуются цепи Р(9) и Р(8). Поскольку v=9 - внешняя вершина, которая имеет метку вершины, то

P(9)=(9, MAT (9))* P(LABEL(9))= (9,10)* P(ll) = (9,10,11, MAT (ll))* P(LABEL(ll)) = (9,10,11,12) * P(4) =

= (9,10,11,12,4) .

Вершина v=8 также является внешней и имеет метку вершины, поэтому P(8) = (8, MAT (8))* P(LABEL(()) = (8,7)* P(LABEL(8)) = (8,7)* P(6)= (8,7,6, MAT (б))* P(LABEL(6)) =

= (8,7,6,5)* P(4) = (8,7,6,5,4) .

Определим теперь цепь Р(5): P(5) = revP(8,5)* P(9) = (5,6,7,8)* (9,10,11,12,4) = = (5,6,7,8,9,10,11,12,4)= ((5,6), (7,8), (9,10), (l1,12),4). По отношению к выделенному паросочетанию нет увеличивающей цепи, поэтому оно является максимальным паросочетанием.

На вход этапа а2 подается граф G1 (рис. 4). Массив OUTER содержит сначала вершины 1, 3, 4. Значения массивов LABEL и FIRST занесем в таблицу 2:

Рис. 5. Работа алгоритма Габова нахождения максимального паросочетания в графе G.

Начальной вершиной является v=1. Массив OUTER содержит сначала вершины 1, 3, 4, 11, 6, 9, 8. Значения массивов LABEL и FIRST занесены в таблицу 3.

Таблица 3.

Зафиксируем вершину v=12, которая имеет метку ребра N(9, 8), тогда цепь p(12) = revP(9,12)*p(8). Вершина v=9 имеет метку вершины, поэтому p(9) = (9,MAT(9)* P(LABEL(9))= (9,10)* P(11)= (9,10,11, MAT (11))* P(LABEL(11)) = (9,10,11,12)* P(4)= (9,10,11,12,4, MAT (4))* P(LABEL(4)) = (9,10,11,12,4,13,1).

паросочетание М = ((5,6); (7,8), (9,10), (11,12);4)*((2,3), (4,13)1) = ((5,6), (7,8), (9,10); (11,12)4; (2,3), (4,13)1), которое является максимальным паросочетанием М исходного графа G. Убедимся в этом рассмотрев работу алгоритма Габова [2] на графе G (рис. 5).

4. Анализ и обоснование алгоритма а

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

Если всем исходным данным задачи присвоить конкретные значения и разместить их в памяти ЭВМ, то эти исходные данные называются входом задачи. Размером (длиной) входа называется число ячеек памяти ЭВМ, занятых входом[5].

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

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

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

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

Вершина v=8 имеет метку вершины, поэтому p(8)=(8,MAT(8))* P(LABEL(8))= (8,7)* * P(6)= (8,7,6, MAT (6))* P(LABEL(6))= (8,7,6,5)* P(4) = (8,7,6,5,4, MAT (4))* P(LABEL(4))= (8,7,6,5,4,13)* *P(l) = (8,7,6,54,13,1). Следовательно, цепь P(l2) = revP(9,12)* P(8) = ((l2,1l); (10,9); (8,7); (6,5); (4,13);l). После дополнения получим новое паросочетание, состоящее из ребер (12, 11); (10, 9); (8, 7); (6, 5); (4, 13); 1 и (3, 2). По отношению к полученному паросочетанию нет увеличивающей цепи, поэтому это паросочетание - максимальное (рис. 5).