Информатика, вычислительная техника
и управление
Системный анализ, управление и обработка информации
Малистов А. С., кандидат технических наук, зам. руководителя отдела ЗАО «ЭЛВИС-НеоТек»
АЛГОРИТМ ПОИСКА ПАРОСОЧЕТАНИЯ НАИБОЛЬШЕГО И НАИМЕНЬШЕГО ВЕСА, ПОКРЫВАЮЩЕГО ЗАДАННЫЕ ВЕРШИНЫ ПРОИЗВОЛЬНОГО ГРАФА
В статье рассматривается обобщение известной задачи о построении максимального взвешенного паросочетания. Предлагается быстрый алгоритм, который строит паросочетание наибольшего (наименьшего) веса в произвольном графе, покрывающее заданные вершины.
Ключевые слова: взвешенное паросочетание, покрытие, теория графов, алгоритм.
AN ALGORITHM FOR FINDING A MAXIMUM AND MINIMUM WEIGHTED MATCHING COVERING GIVEN VERTICES IN GENERAL GRAPHS
We construct an fast algorithm for finding a maximum (minimum) weighted matching in general graphs covering given vertices of a graph.
Keywords: weighted matching, cover, graph theory, algorithm.
Пусть С = (у,E, и») - неориентированный взвешенный граф. Паросочетанием М в графе называется множество рёбер, не имеющих общих вершин. В этой статье мы обобщаем классическую задачу поиска паросочетания максимального веса в графе G. Кроме общей формулировки имеется три частных случая: задача поиска паросочетания в двудольных графах, известная как задача о назначениях, поиск паросочетания максимальной мощности (все ребра имеют единичный вес) или оба ограничения одновременно. Последний случай известен в литературе как задача о свадьбах. Во взвешенном графе каждому ребру я приписан вес = i -: Можно считать, что вес ребра всегда положителен, потому что ребра с отрицательным весом не могут входить в максимальное паросочетание и их можно предварительно отбросить при решении задачи. Обратим также внимание, что задача поиска минимального паросочетания эквивалентна задаче поиска максимального, если поменять знак весов для всех ребер. Для положительных весов исходного графа задача поиска минимального паросочетания имеет тривиальное решение - пустое множество. Однако, иногда задачу о назначениях формулируют в терминах минимизации, требуя поиска совершенного паросочетания минимального веса. Совершенным паросочетанием называется паросочетание, покрывающее все вершины данного графа. Иногда бывает полезно покрыть паросочетанием некоторые вершины, обладающие заданными свойствами. Например, в работе [1] рассматривается частный случай поиска паросочетания наименьшей мощности в двудольном мультиграфе, покрывающего вершины, которые имеют максимальную степень. В [1] указывается, что такое паросочетание можно построить за время где максимальная степень муль-тиграфа, однако сам алгоритм не приводится.
Пусть дан неориентированный взвешенный граф С = {V. Er и»} и некоторое подмножество его вершин U с V. Требуется найти паросочетание максимального (минимального) веса, которое покрывает набор вершин U. Для случая ■£/ = £' мы получаем классическую задачу поиска паросочетания максимальной мощности. Для £/ = !<" мы получаем задачу поиска со-
вершенного паросочетания максимального или минимального веса. Таким образом, мы сформулировали более общую задачу поиска паросочетаний, которая, как покажем ниже, алгоритмически не сложнее классической. Сконструируем новый граф и сведем нашу задачу к задаче поиска максимального взвешенного паросочетания во вновь построенном графе, для которой известен алгоритм, работающий за время f)(yH bg V} [2].
Классическая формулировка задачи поиска паросочетания требует, чтобы веса были действительными числами, которые в свою очередь являются элементами непрерывного упорядоченного поля К. В алгоритме [2] непрерывность и операция умножения не требуется, что приводит нас к выводу, что алгоритм будет работать для любой упорядоченной коммутативной группы. В качестве такой группы возьмем двухэлементный вектор f £ с обычной операцией сложения: ассоциативность, коммутативность, существование единицы и обратного элемента не вызывает сомнений. Введем для указанной группы лексикографический порядок: сперва сравнивается первый элемент, затем второй. Такой порядок удовлетворяет всем аксиомам упорядоченной группы.
Рассмотрим новый взвешенный граф W}, который имеет тот же набор вершин и
рёбер, что и исходный граф, а все веса будут принадлежать выбранной упорядоченной группе.
Алгоритм Nwmax/Nwmin (Построение покрывающего паросочетания максимального/минимального веса). Для неориентированного взвешенного графа G = plSjW) и подмножества его вершин U с ^ алгоритм строит паросочетание М наибольшего (наименьшего) веса, покрывающее все вершины из U.
N1. [Выбор варианта задачи] Для Nmax i е-1 Для Nmin в г--1.
N2. [Инициализация] Для графа JpifijH') установить для каждого ребра е, соединяющего две вершины из If между собой, вес ^(я) е- (Я.* ■ для каждого ребра я, соединяющего вершину из U с вершиной из вес е- ■ а для всех остальных рёбер вес ■ ■(■))
w «- (fc е t/\ + [*- Е lf\rx ■ »(в)),
где [условие] = 1 тогда и только тогда, когда условие истинно.
N3. [Удаление] Удалить ребра с отрицательным весом «С (О/в).
N4. [Построение] Найти паросочетание М максимального веса в графе § [У. Ш, IV_), где веса ребер принадлежат упорядоченной коммутативной группе.
N5. [Возврат значения] Если построенное паросочетание покрывает все вершины из £/, то вернуть М. В противном случае завершить алгоритм неудачей.
Теорема 1 (правильность алгоритма Nwmin/Nwmax). Пусть дан неориентированный взвешенный граф i = (V, Er ir) и подмножество его вершин V. Тогда алгоритм Nwmin/Nwmax завершается успехом и строит паросочетание М максимальной (минимальной) мощности, покрывающее все вершины из II, если такое паросочетание существует. Иначе, алгоритм завершается неудачей.
Доказательство. Вес шОО любого допустимого паросочетания Р в графе равен (■в,? ■ иг{Р)} где и - число вершин в U, которое Р покрывает, a w(i) - вес паросочетания в исходном графе. Если существует покрывающее паросочетание М, то оно будет иметь вес, в котором и — |£/[, а, следовательно, максимальное паросочетание, которое должно иметь вес не меньше, будет иметь такое же значение для и (больше, чем щ, невозможно), откуда следует, что построенное алгоритмом решение должно быть покрывающим. Среди всех покрыва-
ющих паросочетаний будет выбрано то, которое имеет наибольшую вторую часть * ■ Для Nwmax это даст паросочетание с наибольшим весом, а для Nwmin - с минимальным весом. I
Предложенный нами алгоритм для произвольного графа строит паросочетание наименьшей (наибольшей) мощности, покрывающее заданные вершины, за время Ü(YS log К), или позволяет за это время определить, что такого паросочетания не существует.
ЛИТЕРАТУРА
1. Пяткин А. В., «Раскраска инциденторов и другие задачи на графах: алгоритмический аспект». Диссертация на соискание ученой степени доктора физ.-мат. Наук, Новосибирск -
2009.
2. Galil Z., Micali S., Gabow H. An P£_Vf£iIi>g. V) algorithm for finding a maximal weighted matching in general graphs, SIAM Journal on Computing, v.15 n.l, p.120-130, Feb. 1986.
Для дальнейшего прочтения статьи необходимо приобрести полный текст. Статьи высылаются в формате PDF на указанную при оплате почту. Время доставки составляет менее 10 минут. Стоимость одной статьи — 150 рублей.