Естественные и технические науки, № 1, 2015
Малистов А.С., кандидат технических наук, зам. руководителя отдела ЗАО «ЭЛВИС-НеоТек»
АЛГОРИТМ ПОИСКА ПАРОСОЧЕТАНИЯ, ПОКРЫВАЮЩЕГО ЗАДАННЫЕ ВЕРШИНЫ ПРОИЗВОЛЬНОГО ГРАФА
В статье предлагается быстрый алгоритм, который строит паросочетание в произвольном графе, покрывающее заданные вершины.
Ключевые слова:. паросочетание, покрытие, теория графов, алгоритм.
AN ALGORITHM FOR FINDING A MATCHING COVERING GIVEN VERTICES
IN GENERAL GRAPHS
We construct an fast algorithm for finding a matching in general graphs covering given vertices of a graph.
Keywords:. matching, cover, graph theory, algorithm.
Для некоторых практических задач бывает полезно найти паросочетание, которое покрывает вершины графа с заданными свойствами. Например, это могут быть вершины с максимальной степенью. В работе [1] рассматривается частный случай поиска паросочетания наименьшей мощности в двудольном мультиграфе, покрывающего вершины, которые имеют максимальную степень. В [1] указывается, что такое паросочетание можно построить за время где Д- максимальная степень мультиграфа, однако сам алгоритм не приводится. Мы будем решать общую задачу на произвольных графах, для которой предлагаем более быстрый алгоритм нахождения паросочетания, покрывающее заданные вершины. При этом алгоритм будет работать и для мультиграфов, так как из нескольких кратных ребер мы можем оставить одно и рассматривать задачу на обычном графе. Рассмотрим задачу более формально.
Пусть дан неориентированный граф С = (V,iT) и некоторое его подмножество вершин Е/с V. Требуется найти паросочетание в этом графе, которое покрывает набор вершин О. Напомним, что паросочетанием M в графе называется множество рёбер, не имеющих общих вершин. Для того, чтобы найти такое паросочетание мы сведем нашу задачу к известной задаче нахождения паросочетания максимального веса в произвольном взвешенном графе, а затем воспользуемся алгоритмом, который умеет строить это паросочетание за время OfPKhiEt' J [2].
Алгоритм MC (Построение покрывающего паросочетания). Для неориентированного графа S = (F|Jf) и некоторого подмножества его вершин II V алгоритм строит паросочетание M С Б, покрывающее все вершины из или завершается неудачей, если такого паро-сочетания не существует.
МС1. [Инициализация.] Установить для каждого ребра, соединяющего две вершины из U между собой, вес tt^fs") î- 2; для каждого ребра, соединяющего вершину из Ус вершиной из ^\£/, вес е-1, а для всех остальных рёбер вес w(V) ^ 0:
tt<tt,p} i- [it e U\ + [v E lf[r
где [условие] = 1 тогда и только тогда, когда условие истинно.
МС2. [Построение.] Построить максимальное взвешенное паросочетание M во взвешенном графе [2].
Естественные и технические науки, № 1, 2015
МСЗ. [Возврат значения.] Если построенное паросочетание покрывает все вершины из U, то вернуть М. В противном случае завершить алгоритм неудачей.
Теорема 1 (правильность алгоритма МС). Пусть дан неориентированный граф G = (V, Е) и подмножество его вершин U. Тогда алгоритм МС завершается успехом и строит паросочетание М, покрывающее все вершины из ¿/, если такое паросочетание существует. В противном случае, алгоритм завершается неудачей.
Доказательство. Вес любого допустимого паросочетания в графе С = (У, равен числу вершин в [/, которое это паросочетание покрывает. Таким образом, если существует покрывающее паросочетание W, то оно должно иметь вес, равный числу вершин в а, следовательно, максимальное паросочетание должно иметь вес не меньше, откуда и следует, что построенное алгоритмом MC решение, должно быть покрывающим. Таким образом, алгоритм завершается успехом в том и только в том случае, когда покрывающее паросочетание существует. I
Построить покрывающее паросочетание можно за Q(£V L>g V), так как установка весов на первом шаге и проверка на третьем занимает не более О'Ж) шагов. Встаёт разумный вопрос: а бывают ли случаи, когда покрывающего паросочетания не существует? Ответ на этот вопрос утвердительный. Примером может служить граф из пяти вершин, соединённых между собой циклом. Степень каждой вершины равна 2. Если мы потребуем покрыть все вершины графа, то это сделать не удастся. Очевидно, что любое паросочетание может покрыть лишь чётное число вершин, поэтому одна всегда останется свободной.
Предложенный нами алгоритм для произвольного графа строит паросочетание, покрывающее заданные вершины, за время £?CV£rk}-£jl^, или позволяет за это время определить, что такого паросочетания не существует. Оценку времени работы можно еще улучшить до если воспользоваться асимптотически более быстрым алгоритмом поиска максимального взвешенного паросочетания [3].
ЛИТЕРАТУРА
1. Пяткин А. В., «Раскраска инциденторов и другие задачи на графах: алгоритмический аспект». Диссертация на соискание ученой степени доктора физ.-мат. наук, Новосибирск -
2009.
2. Galil Z., Mi cali S., Gabow H. An E?£ralojj V") algorithm for finding a maximal weighted matching in general graphs, SIAM Journal on Computing, v.15 n.l, p.120-130, Feb. 1986.
3. Gabow H.N. «Data structures for weighted matching and nearest common ancestors with linking», in Proceedings of the First Annual ACM-SIAM Symposium on Discrete Algorithms, Association for Computing Machinery, New York, 1990, pages 434-443.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.