15.6. Совершенное паросочетание, оптимальное назначение и составление расписаний

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

соответствующем двудольном графе. Имея это в виду, вначале обсудим алгоритм построения совершенного паросочетания в двудольном графе.

15.6.1. Совершенное паросочетание

Рассмотрим задачу о назначении, в которой рабочих могут выполнить один или несколько из видов работ; необходимо определить, можем ли мы назначить рабочих на все виды работ по одному рабочему на каждый вид работы, который он может выполнить. Если представим рабочих множеством вершин , а виды работ — множеством вершин Двудольного графа G, в котором смежна с у, тогда и только тогда, когда рабочий может выполнить вид работы то ясно, что задача о назначении сводится к задаче определения, имеет ли граф G совершенное паросочетание.

Одним из методов решения этой задачи было бы применение алгоритма 15.6 и выделение максимального паросочетания. Если это паросочетание состоит из ребер, то граф имеет совершенное паросочетание, а полученное максимальное паросочетание есть не что иное, как совершенное паросочетание.

Главным недостатком такого метода является то, что если граф не имеет совершенного паросочетания, то мы узнаем об этом только в конце процедуры. Рассмотрим алгоритм, который находит совершенное паросочетание в графе G либо останавливается, когда находит такое подмножество 5 множества X, что , где множество вершин, смежных с вершинами из подмножества . Из теоремы Холла 8.13 ясно, что в последнем случае в графе не существует совершенного паросочетания.

Основная идея, лежащая в основе этого алгоритма, очень проста. Как обычно, мы начинаем с некоторого начального паросочетания М. Если М насыщает все вершины множества X, то это как раз то паросочетание, которое мы ищем. Иначе в общем случае мы выбираем ненасыщенную вершину и множества X и систематически ищем добавляющий путь Р, начинающийся в и. При поиске такого пути мы запоминаем количество вершин, выбранных из множества X, число смежных с ними вершин и число вершин, выбранных из множества У.

Двудольность графа гарантирует нам то, что мы не получим при поиске цикла нечетной длины и, следовательно, «цветок» не может образоваться. Как мы видели в разд. 15.4.1, замкнутый чередующийся путь четной длины не дает возможности расширить имеющееся паросочетание М. Следовательно, граф поиска, который мы строим, всегда будет деревом. Это дерево называется венгерским деревом. На любом этапе, если мы находим добавляющий путь, мы выполняем дополнение и получаем новое паросочетание, которое насыщает во множестве X на одну вершину больше, чем было до этого. Если

такого пути не существует, что мы получаем множество SX, нарушающее необходимое и достаточное условие существования совершенного паросочетания.

Пусть М — паросочетание в графе — ненасыщенная вершина в X. Дерево Н графа G называется М-чередующимся деревом с корнем и, если 1) и принадлежит множеству вершин Н и 2) для каждой вершины и из Н единственный путь из и в v в Н есть М-чередующийся путь (т. е. чередующийся путь по отношению к М).

Пусть S — подмножество множества вершин а Т - подмножество множества вершин Y, которые встречаются в Н.

Чередующееся дерево «растет» следующим образом. Вначале Н состоит только из вершин и. Затем оно растет таким образом, что на каждом этапе существуют две возможности:

1. Все вершины в , кроме и, насыщены (рис. 15.14, а).

Рис. 15.14. Примеры чередующихся деревьев.

2. Н содержит ненасыщенную вершину, отличную от и (рис. 15.14, б). В этом случае мы получаем добавляющий путь и, следовательно, получаем новое паросочетание.

В первом случае либо

Так как в дереве Н, то мы получаем в этом случае и множество S не удовлетворяет необходимому и достаточному условию теоремы Холла. Следовательно, можно сделать вывод, что в графе G нет совершенного паросочетания.

16. . Тогда существует вершина у из Y, которая не встречается в , но входит в . Путь эта вершина у будет смежна с вершиной из S. Если у насыщена — ее напарник, то мы наращиваем Н, добавляя вершины а также ребра .

Тогда мы вновь возвращаемся к первому случаю. Если у не насыщена, то мы наращиваем , добавляя вершину у и ребро и приходя ко второму случаю. Путь из и в у в Я является добавляющим путем по отношению к М. Метод, описанный выше, реализуется следующим алгоритмом:

Алгоритм 15.7. Совершенное паросочетание.

S1. Пусть G — двудольный граф с разбиением множества вершин (X, Y), где . Пусть пустое паросочетание, т. е. Положить

(см. скан)

Рис. 15.15.

S2. Если все вершины из X насыщены в паросочетании то совершенное паросочетание в графе G.) Иначе выбрать ненасыщенную вершину и в X и положить

S3. Если то HALT. и, следовательно, в графе G нет совершенного паросочетания.) Иначе выбрать вершину у из .

S4. Если у не насыщена то идти к шагу Иначе положить — напарник у, после чего идти к шагу

S5. (Найден добавляющий путь Р). Положить Идти к шагу

В качестве примера рассмотрим двудольный граф G, представленный на рис. 15.15, а. В этом графе ребра начального паросочетания М изображены штриховыми линиями. Вершина в М не насыщена. Строим М — чередующееся дерево с корнем Мы завершаем наращивание дерева в момент, показанный на рис. 15.15, б, где мы разместили добавляющий путь Затем мы расширяем М и получаем новое паросочетание, показанное на рис. 15.15, в.

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

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

15.6.2. Оптимальное назначение

Рассмотрим задачу о назначении, в которой каждый рабочий может выполнить любой вид работы. Очевидно, что в таком случае мы можем каждому рабочему назначить работу (конечно, мы, как и раньше, предполагаем, что имеется рабочих и работ). Фактически любое максимальное паросочетание является совершенным, и мы получим таких паросочетаний. Задача, интересующая нас в этом случае, состоит в учете эффективности назначения рабочих на различные работы и получении такого назначения, которое максимизирует общую эффективность. Задача нахождения такого назначения известна как задача об оптимальном назначении.

Двудольный граф для этой задачи является полным, т. е. если — множество вершин, представляющих рабочих, а — множество вершин, представляющих работы, то для всех i и смежна с У]. Припишем каждому ребру вес который показывает эффективность работы рабочего при выполнении задания у, (измеряемую в каких-либо единицах). Тогда задача об оптимальном назначении соответствует задаче определения в таком взвешенном графе совершенного паросочетания с максимальным весом. Такое паросочетание называется оптимальным.

Рассмотрим алгоритм сложности предложенный Каном и Мункресом [15.40, 15.41] для задачи об оптимальном назначении. Мы будем придерживаться изложения в работе [15.35].

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

Например, следующая разметка является допустимой вершинной разметкой: если если . Из этого следует, что допустимая вершинная разметка всегда существует независимо от значений весов ребер.

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

Следующая теорема, связывающая подграф равенств и оптимальные паросочетания, образует основу алгоритма Кана — Мункреса.

Теорема 15.6. Пусть — допустимая вершинная разметка графа . Если содержит совершенное паросочетание М, то М — оптимальное паросочетание в графе

Доказательство. Предположим, что содержит совершенное паросочетание М. Так как — остовный подграф графа G, то М — совершенное паросочетание в графе G. Пусть — вес М, т. е. . Поскольку каждое ребро принадлежит подграфу равенств и каждая вершина графа G инцидентна точно одному ребру из М, то мы получаем

    (15.28)

С другой стороны, если М — произвольное совершенное паросочетание в графе G, то

Объединяя выражения (15.28) и (15.29), получим Таким образом, М — оптимальное паросочетание в графе

В алгоритме Кана — Мункреса мы начинаем с произвольной допустимой вершинной разметки и определяем соответствующий граф . Затем выбираем начальное паросочетание М в и применяем алгоритм 15.7. Если получается совершенное паросочетание в то, согласно теореме 15.6, это паросочетание оптимально. В противном случае алгоритм 15.7 заканчивается после построения паросочетания , которое несовершенно, получая М — чередующееся дерево Н, не содержащее добавляющего по отношению к пути и не может быть наращено далее в . Тогда мы изменяем f, получая допустимую вершинную разметку с тем свойством, что и и Н содержится в и Н можно расширить в Мы осуществляем такие изменения допустимой вершинной разметки всякий раз, когда это необходимо до тех пор, пока не обнаружим совершенное паросочетание в каком-либо из подграфов равенств. Детали алгоритма Кана — Мункреса представлены ниже.

Алгоритм 15.8. Оптимальное назначение (Кан и Мункрес).

S1. G — данный полный двудольный граф с разбиением множества вершин (X, F), где — заданная матрица весов. Положить

S2. Начать с произвольной допустимой вершинной разметки в графе G. Найти подграф равенств и выбрать начальное паросочетание

S3. Если все вершины в X насыщены в , то — совершенное паросочетание и, следовательно, по теореме 15.6 это — оптимальное паросочетание. HALT. Иначе пусть и — ненасыщенная вершина в X. Положить

S4. Пусть — множество вершин, которые смежны в графе с вершинами из множества S. Если то идти к шагу Иначе (т. е. если ) вычислить

    (15.30)

и получить новую допустимую вершинную разметку определяемую выражением

Отметим, что Заменить на на

S5. Выбрать вершину у из Если у не насыщена в то идти к шагу Иначе положить -напарник у в и идти к шагу

S6. (Найден добавляющий ). Положить Идти к шагу

Чтобы проиллюстрировать алгоритм Кана — Мункреса, рассмотрим полный двудольный граф G, имеющий следующую матрицу весов:

Начальную допустимую вершинную разметку для графа G можно выбрать следующим образом:

Подграф равенств представлен на рис. 15.16, а. Применяя алгоритм 15.6, мы определяем, что не имеет совершенного паросочетания, поскольку для множества Используя выражение (15.30), определяем Тогда, используя выражение (15.31), получаем следующую новую разметку:

Подграф равенств представлен на рис. 15.16, б. С помощью алгоритма 15.6 мы получаем совершенное паросочетание М, состоящее

из ребер Это паросочетание является оптимальным.

Рис. 15.16.

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

15.6.3. Составление расписаний

В школе работают учителей и имеется q классов Известно, что учитель должен провести в классе занятий; необходимо составить расписание таким образом, чтобы время проведения занятия было наименьшим из возможных. Такая задача является частным случаем задачи о составлении расписаний.

Предположим, что мы построили двудольный граф , в котором вершины из X представляют учителей, вершины из Y — классы, а вершина соединена с вершиной параллельными ребрами. Так как в любое время каждый учитель может преподавать не более чем в одном классе и каждый класс может находиться не более чем на одном занятии, то расписание занятий для одного урока соответствует паросочетанию в графе G и наоборот, каждое паросочетание соответствует возможному назначению учителей по классам для проведения одного урока. Таким образом, задача о составлении расписаний, упомянутая выше, есть задача разбиения ребер графа G на возможно меньшее число паросочетаний.

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

равно максимальной степени этого графа G. Доказательство этого утверждения включает следующую процедуру определения разбиения на наименьшее число паросочетаний множества ребер графа: Шаг 1. Пусть G — данный двудольный граф. Положить

Шаг 2. Построить паросочетание графа G, которое насыщает все вершины с максимальной степенью в графе

Удалить из графа . Пусть — получающийся в результате граф. Если не имеет ребер, то — требуемое разбиение множества ребер графа G. Иначе положить и идти к шагу 1.

Ясно, что сложность приведенной выше процедуры зависит от сложности реализации шага 2, который требует определения паросочетания, насыщающего все вершины с максимальной степенью в двудольном графе Такое паросочетание можно найти следующим образом (теорема 8.21):

Пусть — множество вершин с максимальной степенью в — множество вершин с максимальной степенью в Y. Пусть — подграф графа G, образуемый ребрами, инцидентными вершинам из . Аналогично — подграф, образуемый ребрами, инцидентными вершинам из

Согласно теореме 8.22, существует паросочетание которое насыщает все вершины из Паросочетание — максимальное паросочетание в Аналогично в существует максимальное паросочетание которое насыщает все вершины в Следуя процедуре, используемой в доказательстве теоремы 8.21, мы можем получить из паросочетание М, которое насыщает вершины в Тогда М — требуемое паросочетание, насыщающее все вершины максимальной степени в графе

Сложность выделения совпадает со сложностью выделения максимального паросочетания, т. е. где n — число вершин в графе G. Легко показать, что сложность построения М по есть . Таким образом, сложность выполнения шага 2 равна Так как шаг 2 будет повторен А раз, где А — максимальная степень вершин в графе сложность построения требуемого расписания равна

Анализ задачи о составлении расписаний в общем виде и ссылки на литературу по этой проблеме имеются в работе [15.43].