Покажем теперь, что VАс Р" условие (*) теоремы записывается в следующем виде: п(Г)< \Vy\- (И — ЛЛ). Тогда ранее найденное множество В, для которого данное неравенство обращается в равенство, будет доказательством условия (*) теоремы. Пусть Ау = А(оз пЛ),тогдаА = (ю глА) иАу. Отметим, что ЧЛХ сЩ** глАу) выполняется неравенство \АХ\< Л/1,, так как вершины множества РД(ю n Vx) составляют паросочетание. Тогда верно, что И=+ \АХ\< ю + \АХ\< ю + \ААу\< ш + \АА] или \А\- АА\< со.

Теперь количество ребер в максимальном паросочетании можно оценить: я(Г)=К[— со< \Vy\— (\А\ — Л/1). Теорема доказана.

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

Рассмотрим пять множеств: Sy = {2, 3}, S2 = {1,2, 4}, S3 = {1,2, 5}, J4 = {3, 4, 5}, S5 = {3, 4, 5}. Требуется выбрать такие различные числа, х2,х3, х4,х5, чтох,-е Sj,i = 1,2,...,5. Дляданногопримерах! = 2, х2 = 1, х3 = 5, х4 = 3, х5 =4. Однако если взять множества ={1,2}, Т2 = {1,2}, Г3={1,2}, 74={3,4,5}, Т5 = {3, 4,5}, то такой выбор оказывается невозможным.

Рассмотрим данную задачу в общем случае. Пусть S = {1, 2,..., и}. M(S) — система подмножеств Sy, S2,..., Sn множества S. Будем говорить, что M(S)имеет систему различных представителей, если для всех / 1,2,..., п существуют различные х,- е Щ.

6.14.5. Связь системы различных представителей и двудольных графов

Определим двудольныйграф

Г= (Vy<uV2, U, Ф), соответствующий системе подмножеств. Пусть M(S) = {Su S2,..., Sn) — система подмножеств Sb S2,..., Sn множества S. Положим Sb S2,..., „вершинами Vy графа, которые соединены ребрами со своими элементами — смежными им вершинами из К2(рис. 6.51).Рис- 6-51

• Лемма 6.14.1. Двудольный граф Г= (Vy иК2Д Ф), отвечающий системе подмножеств = {Sy, S2,..., Sn}, имеет максимальное паросочетание из п ребер тогда и только тогда, когда M(S) имеет систему различных представителей. (Доказательство вытекает из определения построения двудольного графа, отвечающего системе различных представителей).

• Теорема 6.14.3 Ф. Холла о существовании системы различных представителей. Система M(S)= {SUS2,..., S„} имеет систему различных представителей тогда и только тогда, когда для любой подсистемы {St ,Sj ,...,S: } с М(S)выполняетсянеравен-

к 1

ство [)Sj >к, т.е. количество элементов в объединении лю-

И I

к подмножеств должно быть не менее к.

Необходимое условие теоремы следует из определения системы различных представителей. Каждое подмножество Sj е M(S содержит элемент дг е 5", , отличный от

К

элементов других подмножеств, а значит I IS, > к.

т 1

Ф)соответству-

ющий системе подмножеств = {SS2,..., Sn). Покажем, что в данном графе существует максимальное паросочетание, количество ребер в котором равно п. Тогда из леммы 6.14.1 будет следовать достаточное условие теоремы. Из теоремыимеем, что число ребер в максимальном паросочетании равно = ii — -тах(Л-А4), где/VI = {уе У: \3jcs 1, л (х, у) е U с В рамках принятой интерпретации A ={S,,Si2,...,S }, \A\ = к и к

АА = (J Sr . По условию теоремы \АА\ > к. Таким образом, У Ac Vx 7=1

\а\ - \аА\< О, а значит, тг(/) =Щ - тах(И -ДЛ) > VI Однако

;п/ ) < следовательно, гс( Г = Ii = л (достаточное условие доказано).

6.14.6. Задача о назначениях

Существует множество задач, постановки которых укладываются в рамки задачи о назначениях. Рассмотрим две такие постановки.

Задача. Предположим, что вычислительная сеть объединяет п специализированных ЭВМ. На вход сети поступают задачи. Известно, что наибольшая производительность конкретной ЭВМ сети достигается на определенном классе задач. Это выражается коэффициентом использования ЭВМ прикласса за-

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

•Задача. Группа лиц может выполнить п видов работ. Эффективность использования лица на у"-й работе определяется мерой ценности «,у. Найти оптимальную расстановку людей по видам работ.

• Теорема 6.14.4 — алгоритм поискаоптималъной перестановки я.

Пусть А = \аЛ, i,j= \,n — матрица целых чисел. Тогда максимум

тахх(6.14.1)

по всем перестановкам я равен минимуму

min

1=1 у=1 )

(6.14.2)

по всем числам и таким, что

щ + VjbOy, V/,y=l7n.(6.14.3)

Минимум суммы (6.14.2)достигается на перестановке я такой, что

Доказательство. Пусть я — произвольная перестановка. При изменении от 1 до л величины принимают все значения множества {1, 2,..., п). По условию +vt> Оц, V/,y= 1, п, а значит, и для у = ш,верно Ы; + у =«%: .Установим связь сумм (6.14.1) и (6.14.2).

пЛЯАЯя

Shi +Svy =]Ел +Svt, =Zw( +vk, )Хам,

#=I y=l /«1 ;=1 Hi/=1

Таким образом, сумма (6.14.1)для любой перестановки я не больше суммы (6.14.2). Отсюда следует, что теорема будет верна, если мы найдем такие щ и Vj и перестановку я, что (6.14.1) и (6.14.2) совпадают.

Жаг 0. Поиск начальных и v;, удовлетворяющих ограничениям щ г + Vj > ay, V/,y = 1, п. Положим Vj = О и и, = max а у - максима-

j

льный элемент в /-й строке; условие (6.14.3) ut +V[ =maxo(;/ довыполняется. Для матрицы ценностей на рис. 6.52 справа и снизу указаны начальные значения, соответственно и