Тексты лекций / Текст лекции 15

§ 3.ДОП. Паросочетания в двудольных графах

Алгоритм поиска в ширину на ориентированных графах. Паросочетания: наибольшее, максимальное, совершенное. Задача о поиске наибольшего парососчетания в двудольном графе: постановка и алгоритм решения задачи. Задача о поиске совершенного паросочетания минимального веса (задача о назначениях): постановка и алгоритм решения задачи.

Базовые понятия и утверждения

1. Алгоритм поиска в ширину на ориентированных графах.

Всякая конечная последовательность элементов произвольной природы называется списком, а число элементов списка – его длиной. Список называется очередью, если все удаления элементов списка производятся с одного конца, а добавления - с другого.

Пусть граф - ориентированный граф. Поиск в ширину из вершины ( ) – метод обхода (и присвоения меток) всем вершинам графа, достижимым из этой вершины.

Введем в рассмотрение очередь , элементами которой являются вершины графа . Вершине , из которой начинается поиск, присваиваетсяномер1. Эта вершина помещается в очередь и с этого момента считается просмотренной. Затем все вершины, являющиеся концами дуг с началом включаются в очередь, получают статус просмотренных и в порядке включения в очередь нумеруются, а вершина из очереди удаляется. На произвольном шаге, пусть в начале очереди находится вершина . Обозначим через , ,…, вершины, являющиеся концами дуг с началом в и еще не просмотренные. Тогда вершины, ,…, помещаются в очередь и с этого момента считаются просмотренными, а вершина из очереди удаляется и получает статус использованной.

Каждую из дуг ( = 1,…, ) назовем древесной дугой. Процесс обхода в ширину из вершины будем сопровождать построением ориентированного дерева с корнем и древесными дугами. Этому дереву дадим название дерева поиска в ширину. Если – вершина,

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

2. Понятие о паросочетании. Пусть = ( ,) неориентированный граф. Определение. Произвольное множество, состоящее из попарно несмежных ребер

1

Тема 15. «Паросочетания в двудольных графах» Олейник Т.А., 2020

Определение. Паросочетание называется максимальным, если оно не содержится в паросочетании с большим числом ребер.

Например, для графа на рис.1паросочетания { , },{ , }, { , , }-максималь- ные, а { } – нет (оно содержится в { , }).

Определение. Реберным покрытием графа = ( ,)называется такое подмножестворебер, что каждая вершина из инцидентна по крайней мере одному ребру (говорят, что покрывает ).

Например, для графа на рис. 1 множества { , , }, { , , , } являются реберными покрытиями.

Определение. Паросочетание называется совершенным, если оно одновременно является реберным покрытием графа.

Например, для графа на рис. 1 множество { , , }является реберным покрытием,

а { , , , } – нет.

Рассматривая различные задачи о паросочетаниях, мы ограничимся случаем двудольных графов.

Приведемнесколько примеровпрактическихзадач,которыесвязаныспостроением паросочетаний различного вида в двудольных графах.

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

2.Пусть в предыдущей задаче числорабочих и числоработ одинаковои равно . Спрашивается, можно ли так распределить работы между рабочими, чтобы были выполнены все виды работ?

3.Пусть в дополнение к условиям второй задачи для каждой пары рабочий-работа известна стоимость ( ,)выполнения рабочим работы . Требуется так подобрать каждому рабочему определенный вид работы, чтобы суммарная стоимость выполнения всех работ была минимальна.

Построим математические модели приведенных задач. Определим двудольный граф

выполнятьработу .Пусть – паросочетаниевпостроенномграфе ( ,).Тогдакаждое ребро = можно трактовать как назначение рабочему работы .

Впервой задаче распределение работ между рабочими, при котором выполнено наибольшее количество работ, можно интерпретировать как поиск наибольшего паросочетания.

Во второй задаче при дополнительном условии = нужно выяснить, существует или нет совершенное паросочетание на графе.

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

2

Тема 15. «Паросочетания в двудольных графах» Олейник Т.А., 2020

3. Задача построения наибольшего паросочетания. Дан обыкновенный двудольный граф ( ,) с долями = { , ,…, } и = { , ,…, }. Требуется найти в графе наибольшее паросочетание.

Пусть – паросочетание в графе .

Определение. Цепь графа , ребра которой поочередно входят и не входят в , называется чередующейся относительно .Цепь длины 1 поопределению также чередующаяся. Ребра цепи называются темными, если они входят в , и светлыми, если они не входят в. Вершины графа, инцидентные ребрам из , называются насыщенными, все другие вер-

шины – ненасыщенными.

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

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

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

Будем для поиска увеличивающих относительно цепей использовать алгоритм поиска в ширину для ориентированных графов. Для этого поставим в соответствие графу ( ,) и паросочетанию вспомогательный ориентированный двудольный граф , придав ориентацию «от к » всем ребрам графа, входящим в паросочетание, и «от к » всем остальным ребрам этого графа. Обозначим через и множества ненасыщенных вершин, входящих соответственно, в и . Очевидно следующее утверждение: в графе увеличивающая относительно паросочетания цепь существует тогда и только тогда, когда в графе существует ориентированная цепь с началом в вершине из и концом в вершине из .

3

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

1.Построить какое-либо максимальное паросочетание в графе .

2.По графу и паросочетанию построить граф .

3. Пусть в графе - множество вершин из и - множество вершин из , не насыщенных текущим паросочетанием. Если хотя бы одно из этих множеству пусто, то

– наибольшее паросочетание; конец. Иначе выполнить в графе поиск в ширину из множества .

4. Если в результате поиска в ширину ни одна из вершин множества не получила метки, то перейти к п. 5. Иначе перейти к п. 6.

конец цепи – вершина из (найденный в результате поиска в ширину в п. 4). Изменить граф , заменив в нем каждую дугу ( ,)цепи на дугу ( ,). Перейти к п. 3.

4. Задача построения совершенного паросочетания в двудольном взвешенном графе. Дан полный двудольный взвешенный граф ( ,) с одинаковыми по мощности долями = { , ,…, } , = { , ,…, }. Требуется найти в графе совершенное паросочетание наименьшего веса. Поставленную задачу называют задачей о назначениях.

Совершенное паросочетание минимального веса назовем для краткости оптимальным решением.

Будем считать, что граф задан матрицей, в которой строк, столбцов и элемент, стоящий на пересечении -ой строки и -ого столбца, равен весу ребра, соединяющего -ую вершину первой доли с -ой вершиной второй доли. Эту матрицу называют матрицей весов двудольного графа.

Задача о назначениях обладает двумя простыми свойствами:

1.Поскольку для каждой вершины любое совершенное паросочетание содержит в точности одно ребро, инцидентное этой вершине, то множество оптимальных решений не изменится, если веса всех ребер, инцидентных какой-либо вершине, увеличить (уменьшить) на одно и то же число.

2.Если веса всех ребер неотрицательны и вес некоторого совершенного паросочетания равен нулю, то оно является оптимальным решением.

Пусть ( ,) – вес ребра . Будем считать, что ( ,) ≥ 0 для каждого ребра графа . Из первого свойства следует, что случай, когда имеются ребра отрицательного веса,сводитсякнашему.Крометого,этосвойствопозволяетперейти квзвешенномуграфу, у которого каждой вершине инцидентно ребро нулевого веса и веса всех ребер неотрицательны. Для этого достаточно изменить матрицу весов графа следующим образом: сначала вычесть из всех элементов каждой строки минимальный элемент этой строки, а затем тоже самое проделать со столбцами. Будем считать, что эта операция уже проделана и графобладает требуемыми свойствами.

Пусть и − некоторое число. Будем считать, что к графу применяется операция ( ,,), если сначала из веса каждого ребра, инцидентного вершине из множества , вычитается , а затем к весу каждого ребра, инцидентного вершине из множества, прибавляется . Согласно свойству 1 получившийся в результате взвешенный граф

4

Тема 15. «Паросочетания в двудольных графах» Олейник Т.А., 2020

имеет то же множество оптимальных решений, что и граф . Кроме того, ребра вида , где , , в преобразованном графе будут иметь те же веса, что и в исходном.

Заметим,что операция ( ,,) следующим образом изменяет матрицу весов: сначала из всех элементов строк, соответствующих вершинам множества вычитается , а затем ко всем элементам столбцов, соответствующих вершинам из , прибавляется .

Пусть ( ,) - двудольный граф с долями , и - паросочетание в нем.

Будем, как и ранее, обозначать через - вспомогательный ориентированный двудольный граф, полученный из графа путем ориентаций «от к » всех ребрам паросочетанияи «от к » всем остальным ребрам этого графа.

Алгоритм построения совершенного паросочетания минимального веса в дву-

ном графе ). Иначе перейти к п. 4.

7.Пусть ′ и ′ - подмножества вершин графа , получивших пометки в результатепоискавширину(вп.4).Средиреберграфа ,имеющихвид ,что , \ ′ найти ребро минимального веса. Пусть – вес этого ребра.

8.Модифицировать веса ребер графа , применив к нему операцию ( , ,).

9.Модифицировать граф , добавив к нему все такие дуги ( ,), что , \ , ( ,) = 0, и удалив все такие дуги ( ,), что \ , . Перейти к п. 4.

Литература

Емеличев В.А., Мельников О.И., Сарванов В.И., Тышкевич Р.И. Лекции по теории графв: Учебное пособие, Изд. Стереотипно. М.: Книжный дом «Либроком», 2014. – 392 с.

5