Задачи для самостоятельной работы

Задача о наибольшем паросочетании в двудольном графе

Пусть G=(X,U) - произвольный неограф. Паросочетанием будем называть множество несмежных ребер графа G.

U₂ U₅

U₃ U₉

U₁ U₆ U₈

U₄ U₇

Рис. 4.1. Граф G

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

Рассмотрим задачу построения паросочетаний в двудольном графе. Напомним, что граф G=(X,U) называется двудольным, если множество X можно разбить на два непересекающихся подмножества так, что никакие две вершины каждого подмножества не являются смежными. Будем обозначать такой граф G=(X₁, X₂, U).

Пример 1. Пусть задан двудольный граф G=(X,Y,U), где X - множество юношей, Y - множество девушек, а ребро юноша x и девушка y знакомы друг с другом. Каково наибольшее количество танцевальных пар, которые можно составить из знакомых юношей и девушек? Это задача о наибольшем паросочетании в двудольном графе (рис. 4.2), и одно из возможных решений – множество .

Пример 2. Пусть - множество исполнителей, а - множество заданий, причем каждый исполнитель может выполнять некоторые задания множества Y. Затраты на выполнение задания исполнителем обозначим . Требуется назначить каждому исполнителю одно задание так, чтобы суммарные затраты были минимальными. Здесь речь идет о построении наибольшего паросочетания с минимальным суммарным весом.

Y₁

X₁

Y₂

X₂

Y₃

X₃ Y₄

Рис. 4.2. Граф G примера 1

Рассмотрим алгоритм построения наибольшего паросочетания, основанный на теории чередующихся цепей.

Пусть G=(X,Y,U) - двудольный граф без изолированных вершин, и W - некоторое паросочетание в G. Ребра этого паросочетания будем называть темными, а все оставшиеся ребра графа G (т.е. ) будем называть светлыми.

Цепь будем называть чередующейся, если все ее ребра поочередно являются темными или светлыми.

Вершина графа G называется ненасыщенной, если она неинцидентна ни одному темному ребру.

Теорема. Если паросочетание W является наибольшим, то в графе G нет чередующейся цепи, соединяющей две ненасыщенные вершины.

МОП. Пусть W - наибольшее паросочетание и в графе G есть чередующаяся цепь, соединяющая две ненасыщенные вершины. В такой цепи первое и последнее ребра – светлые, количество ребер – нечетное, поэтому светлых ребер в цепи на одно больше, чем темных. Проведем инверсию, поменяв темные ребра на светлые и наоборот. При этом получим новое паросочетание W’, в котором ребер на одно больше, чем в исходном паросочетании W, следовательно паросочетание W не было наибольшим.

Алгоритм построения наибольшего паросочетания.

Шаг 1. Строим некоторое максимальное паросочетание.

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

Шаг 3. В обнаруженной чередующейся цепи проводим инверсию ребер и выполняем шаг 2.

Пример выполнения алгоритма для графа (рис. 4.3):

x₁ y₁

x₂ y₂

x₃ y₃

Рис. 4.3. Построение наибольшего паросочетания

1) исходное паросочетание

2) чередующаяся цепь (подчеркнуты светлые ребра) соединяет ненасыщенные вершиныи ;

3) инвертируем цепь и строим новое паросочетание , которое является наибольшим.

При реализации алгоритма на ЭВМ разбиению ребер на темные и светлые можно сопоставить ориентацию ребер, т.е. , где

Тогда графу G (рис. 4.3) будет сопоставлен орграф G₀ (рис. 4.4), для которого множество ненасыщенных вершин определяется как множество - объединение множества вершин из X с нулевой полустепенью захода и множества вершин из Y с нулевой полустепенью исхода:

x₁ y₁

x₂ y₂

x₃ y₃

Рис. 4.4. Орграф G₀.

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

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

Рис. 5.1. Графы задачи 5.1.

5.2. Нарисуйте графы, дополнительные графам, изображенным на рис. 5.1; запишите для дополнительных графов матрицы смежности; найдите наибольшее ВУМ, пользуясь алгоритмом «общипывания» графа; сравните результаты с результатами задачи 5.1.

5.3. Найдите хроматическое число и постройте одну из возможных раскрасок для данных графов (рис. 5.1).

5.4. Для графов, заданных матрицами смежности (рис. 5.2.) постройте функцию Гранди.

а) б)

Рис. 5.2. Матрицы смежности

5.5. Для данных двудольных графов (рис 5.3.) постройте наибольшее паросочетание, пользуясь алгоритмом (стр. 11).

Рис. 5.3. Двудольные графы

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