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

 

Простая цепь С ненулевой длины в G, ребра которой попеременно лежат и не лежат в Р, называется чередующейся цепью (относительно паросочетания Р).

Эта цепь С называется Р-увеличителем, если первое и последнее ребро цепи С лежат вне Р.

С помощью Р-увеличителя паросочетание Р можно переделать в другое паросочетание Р^* для G с числом ребер в Р^* на единицу больше, чем в Р. Для этого достаточно все ребра в С, лежащие вне Р, добавить к Р, а ребра в С, лежащие в Р, удалить из Р. Для получившегося паросочетания Р^* можно снова искать увеличитель, и так далее, последовательно расширяя получающиеся паросочетания, пока это возможно.

 

Алгоритм

построения совершенного паросочетания

для двудольного графа

 

Данные: матрица смежности двудольного графа G = (U,V, X)

Результат: матрица смежности совершенного паросочетания или множество ребер (дуг), входящих в совершенное паросочетание

 

1. Выберем исходное паросочетание P₁, например одно ребро графа G.

2. Предположим, что паросочетание P_i=(U_i,V_i,X_i) для графа G построено. Построим паросочетание P_i+1 для G следующим образом: выбираем u из U, не принадлежащую P_i, например u₁. Если такой вершины u нет, то P_i есть совершенное паросочетание. Строим в G чередующуюся цепь m_i = [u₁,v₁,u₂,v₂,...u_p,v_p] с u₁=u, в которой всякое ребро (u_i,v_i) не принадлежит X_i, а всякое ребро (v_i,u_i+1) принадлежит X_i. Если такой цепи нет, то совершенного паросочетания граф G не имеет, а паросочетание P_i является для G максимальным (тупиковым). Цепь m_i есть P_i-увеличитель.

3. Выбрасываем из P_i все ребра (v_i,u_i+1) и добавляем все ребра (u_i,v_i) цепи m_i. Получившееся паросочетание P_i+1 на одно ребро длиннее паросочетания P_i. Переходим к п.1.

 

Пример. Построим совершенное паросочетание для двудольного графа G = (U,V, X), U={u₁,u₂,u₃,u₄,u₅,u₆}, V={v₁,v₂,v₃,v₄,v₅,v₆,v₇}, матрица смежности которого имеет вид

 

 

 

v₁ v₂ v₃ v₄ v₅ v₆ v₇

u_{1 1 1 0 0 1 0 0}

u_{2 1 0 1 0 1 0 0}

u_{3 1 0 0 0 0 1 0}

u_{4 0 0 1 1 0 1 1}

u_{5 0 0 0 0 1 0 1}

u_{6 0 0 0 1 0 1 1}

Шаг 1. Выбираем исходное паросочетание Р₁={u₁,v₁}.

V₁ V₂ V₃ V₄ V₅ V₆ V₇

 

 

 

U₁ U₂ U₃ U₄ U₅ U₆

Шаг 2. Выберем вершину u₂, которая не входит в паросочетание P₁, но которая смежна с вершиной v₁, содержащейся в P₁. Далее ищем вершину v, смежную с вершиной u₁, содержащейся в Р₁. В результате получим чередующуюся цепь:

m₁= [u₂,v₁,u₁,v₂]

0 1 0

1 0 1

Единица в первой строке из нулей и единиц означает, что соответствующее этой единице ребро {v₁,u₁} лежит в P₁. Убираем это ребро из P₁, а вместо него добавляем ребра {u₂,v₁}, {u₁,v₂}, соответствующие единицам второй строки. В результате получим паросочетание P₂ ={ {u₁,v₁}, {u₂,v₃} }, число ребер в котором на одно больше, чем в P₁.

Шаг 3.

V₁ V₂ V₃ V₄ V₅ V₆ V₇

 

 

 

U₁ U₂ U₃ U₄ U₅ U₆

Найдем чередующуюся цепь:

m₂= [u₃,v₁,u₂,v_3,]

0 1 0

1 0 1

P₃={ {u₁,v₂}, {u₂,v₃},{u₃,v₁}}.

 

 

Шаг 4.

V₁ V₂ V₃ V₄ V₅ V₆ V₇

 

 

 

U₁ U₂ U₃ U₄ U₅ U₆

Найдем чередующуюся цепь:

m₃= [u₄,v₃,u₂,v₃]

0 1 0

1 0 1

 

P₄={ {u₁,v₂}, {u₂,v₅},{u₃,v₁},{u₄,v₃}}.

 

Шаг 5.

V₁ V₂ V₃ V₄ V₅ V₆ V₇

 

 

 

U₁ U₂ U₃ U₄ U₅ U₆

Найдем чередующуюся цепь:

m₄ = [u₅,v₅,u₂,v_1,u₃,v₆]

0 1 0 1 0

1 0 1 0 1

P₅={ {u₁,v₂}, {u₂,v₁},{u₃,v₆},{u₄,v₃},{u₅,v₅}}.

 

Шаг 6.

V₁ V₂ V₃ V₄ V₅ V₆ V₇

 

 

 

U₁ U₂ U₃ U₄ U₅ U₆

Найдем чередующуюся цепь:

m₅= [u₆,v₆,u₃,v_1,u₂,v₃,u₄,v₇]

0 1 0 1 0 1 0

1 0 1 0 1 0 1

 

V₁ V₂ V₃ V₄ V₅ V₆ V₇

 

 

 

U₁ U₂ U₃ U₄ U₅ U₆

 

P₆={ {u₁,v₂}, {u₂,v₃}, {u₃,v₁}, {u₄,v₇},{u₅,v₅},{u₆,v₆}}. Полученное паросочетание является совершенным для исходного графа.

 

Задача26. Решить задачу нахождения совершенного паросочетания в двудольном графе, используя алгоритм чередующихся цепей.

 

2.2.1. Системы различных представителей

 

Пусть <A₁,…,A_n> - произвольная последовательность множеств (необязательно непересекающихся и необязательно различных). Системой различных представителей для <A₁,…,A_n> будем называть такую произвольную последовательность <а₁,…,а_n>, что и . Мы будем говорить, что в такой системе различных представителей элемент a_i представляет множество A_i. Проблема существования и построения системы различных представителей известна во многих неформальных постановках. Одна из них – это так называемая «задача о комиссиях». Имеется n комиссий, причем A_i – множество членов i-й комиссии. Нужно в каждой комиссии выбрать председателя так, чтобы ни один человек не был председателем более чем в одной комиссии.

Нетрудно заметить, что задача о комиссиях сводится к частному случаю «задачи о назначениях». Действительно, создадим множества

,

(элементы x₁,…,x_m, y₁,…,y_n попарно различны) и

.

Очевидно, что каждая система различных представителей <а₁,…,а_n> однозначно соответствует паросочетанию мощности n в двудольном графе D = (X,Y,E).

 

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