работа по курсу «Дискретная математика» Тема: Разработка алгоритма и программного обеспечения для решения прикладной задачи теории графов (стр. 10 из 11)

и φ_М (x)=0 для остальных дуг x сети S(G); потоку φ величины k соответствует паросочетание М_φ, |М_φ|=k, определяемое следующим образом:

М_φ = {(v,u)| vÎV₁ & uÎV₂ & φ(v,u)=1}.

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

Рис.3.

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

ЗАДАНИЕ 25. Решить задачу нахождения наибольшего паросочетания в двудольном графе, сведя ее к задаче построения максимального потока в транспортной сети и используя алгоритм меток для построения максимального потока.

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

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

Простая цепь С ненулевой длины в 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₇