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

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).