научная статья по теме АЛГОРИТМ ПОИСКА ПАРОСОЧЕТАНИЯ НАИБОЛЬШЕЙ И НАИМЕНЬШЕЙ МОЩНОСТИ, ПОКРЫВАЮЩЕГО ЗАДАННЫЕ ВЕРШИНЫ ПРОИЗВОЛЬНОГО ГРАФА Общие и комплексные проблемы естественных и точных наук

Текст научной статьи на тему «АЛГОРИТМ ПОИСКА ПАРОСОЧЕТАНИЯ НАИБОЛЬШЕЙ И НАИМЕНЬШЕЙ МОЩНОСТИ, ПОКРЫВАЮЩЕГО ЗАДАННЫЕ ВЕРШИНЫ ПРОИЗВОЛЬНОГО ГРАФА»

Естественные и технические науки, № 1, 2015

Малистов А.С., кандидат технических наук, зам. руководителя отдела ЗАО «ЭЛВИС-НеоТек»

АЛГОРИТМ ПОИСКА ПАРОСОЧЕТАНИЯ НАИБОЛЬШЕЙ И НАИМЕНЬШЕЙ МОЩНОСТИ, ПОКРЫВАЮЩЕГО ЗАДАННЫЕ ВЕРШИНЫ ПРОИЗВОЛЬНОГО ГРАФА

В статье предлагается быстрый алгоритм, который строит паросочетание наименьшей (наибольшей) мощности в произвольном графе, покрывающее заданные вершины.

Ключевые слова:. паросочетание, покрытие, теория графов, размер паросочетания.

AN ALGORITHM FOR FINDING A MAXIMUM AND MINIMUM MATCHING COVERING GIVEN VERTICES IN GENERAL GRAPHS

We construct an fast algorithm for finding a minimal (maximal) matching in general graphs covering given vertices of a graph.

Keywords:. matching, cover, graph theory, cardinality.

Поиск максимального паросочетания в графе является одной из классических задач в теории графов и находит применение при решении множества практических проблем. Напомним, что паросочетанием М в графе называется множество рёбер, не имеющих общих вершин. Максимальное паросочетание -это такое паросочетание, которое содержит наибольшее число рёбер. Мы рассмотрим особый случай поиска паросочетания в графе: поиск паросочетания, покрывающего заданные вершины. Так как покрывающих паросочетаний может быть несколько, то будем рассматривать две задачи: поиск покрывающего паросоче-тания максимальной или минимальной мощности. В работе [1] рассматривается частный случай поиска паросочетания наименьшей мощности в двудольном мультиграфе, покрывающего вершины, которые имеют максимальную степень. Мы рассматриваем задачу в более общем виде для произвольных графов и строим более быстрый алгоритм нахождения паро-сочетания максимальной или минимальной мощности, покрывающего заданный набор вершин. Рассмотрим задачу более формально.

Пусть дан неориентированный граф С = и некоторое подмножество вершин

Е/с V. Требуется найти паросочетание в этом графе, которое покрывает набор вершин Ü, и при этом имеет максимальную (минимальную) мощность. Для случая U — 0 мы получаем классическую задачу поиска паросочетания максимальной мощности. Минимальное паросочетание для U =0 тривиально, так как равно пустому множеству. Если набор покрываемых вершин II не пустой, то поиск минимального покрывающего паросочетания приобретает смысл. Для того, чтобы найти такое паросочетание, мы сведем нашу задачу к известной задаче нахождения паросочетания максимального веса в произвольном взвешенном графе, а затем воспользуемся алгоритмом, который умеет строить это паросочетание за время + t^lffjF} [2]. Рассмотрим новый взвешенный граф E\,W), который имеет тот же набор вершин. Для варианта максимизации граф Q будет содержать те же ребра, что и исходный граф С (£"' — Я). Для варианта минимизации мы не будем включать в Е' ребра, которые соединяют вершины из Такие ребра не могут входит в минимальное паросочета-ние, так как такое паросочетание можно уменьшить без ущерба оставить непокрытыми вершины из U.

Алгоритм Nmax/Nmin (Построение максимального/минимального покрывающего паросочетания). Для неориентированного графа С = (X-iTj и подмножества вершин i/c/

Естественные и технические науки, № 1, 2015

алгоритм строит иаросочетание наибольшей (наименьшей) мощности M £ S", покрывающее все вершины из U.

N1. [Выбор варианта задачи] Для Nmax установить ¿ «-1, В. Для Nmin установить s е- О, Е* *- iCtir*0 S В I it S U liV Е £/}. Присвоить n *- \ V\.

N2. [Инициализация] Для графа ffPi^1,») установить для каждого ребра е, соединяющего две вершины из U между собой, вес w(i) t- 2п + 1, для каждого ребра fi, соединяющего вершину из У с вершиной из вес 1 « I -э, а для всех остальных рёбер вес wfe) s:

wfcv) s- n- hi € ïï] +»■ [v E ¿л + bi.v€ ¿л + у - [« Uv Й E/l,

где [условие] = 1 тогда и только тогда, когда условие истинно.

N3. [Построение] Построить максимальное взвешенное паросочетание M в графе Ç(Vrtrm [2].

N4. [Возврат значения] Если построенное паросочетание покрывает все вершины из £/, то вернуть М. В противном случае завершить алгоритм неудачей.

Теорема 1 (правильность алгоритма Nmin/Nmax). Пусть дан неориентированный граф G = (7, Е) и подмножество его вершин U. Тогда алгоритм Nmin/Nmax завершается успехом и строит паросочетание M максимальной (минимальной) мощности, покрывающее все вершины из если такое паросочетание существует. В противном случае, алгоритм завершается неудачей.

Доказательство. Вес любого допустимого паросочетания Р в графе равен шг. 4 Ь,

где и - число вершин в У, которое Р покрывает, a if - число рёбер в Р для Nmax или число ребер, соединяющих две вершины из О, для Nmin. При этом и - целая часть от деления веса wÎP") на 'п, а & < it - остаток от деления на л. Если существует покрывающее паросочетание М, то оно будет иметь вес, в котором щ = |У|, а, следовательно, максимальное паросочетание, которое должно иметь вес не меньше, будет иметь такое же значение для и, откуда и следует, что построенное алгоритмом решение должно быть покрывающим. Среди всех покрывающих паросочетаний будет выбрано то, которое имеет наибольший остаток к Для Nmax это даст паросочетание с наибольшим количеством ребер, а для Nmin - с максимальным числом ребер, соединяющих две вершины из V, что приводит к минимизации общего числа ребер. ■

Предложенный нами алгоритм для произвольного графа строит паросочетание наименьшей (наибольшей) мощности, покрывающее заданные вершины, за время £Г(У£"Ч- V* L&jt^, или позволяет за это время определить, что такого паросочетания не существует.

ЛИТЕРАТУРА

1. Пяткин А. В., «Раскраска инциденторов и другие задачи на графах: алгоритмический аспект». Диссертация на соискание ученой степени доктора физ.-мат. Наук, Новосибирск -2009.

2. 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 рублей.

Показать целиком