F (z) в остальных случаях,

где d_f = min{f (x)+ f (y) - w(x, y)}

x S

y ГS

Пример 8. Построить оптимальное паросочетание для двудольного графа, заданного матрицей весов:

5 4 4 3

W = 4 3 3 2

3 2 2 1

2 1 1 1

Определим допустимую вершинную разметку

f(x₁) = 5, f(у₁) = 0,

f(x₂) = 4, f(у₂) = 0,

f(x₃) = 3, f(у₃) = 0,

f(x₄) = 2, f(у₄) = 0,

Граф равенств G_f изображен изображен на рис.24. Совершенное паросочетание построить не удается, при этом S ={x₁, x₂, x₃, x₄} и ГS ={y₁}.

f(x) f(y) f(x) x₁ y₁ f’(y)

5 x₁ ○ ○ y₁ 0 4 ○ ○ 1

x₂ y₂

4 x₂ ○ ○ y₂ 0 3 ○ ○ 0

x₃ y₃

3 x₃ ○ ○ y₃ 0 2 ○ ○ 0

x₄ y₄

2 x₄ ○ ○ y₄ 0 1 ○ ○ 0

Рис. 24 Рис. 25

Определим новую допустимую разметку f’:

f’(x₁) = 4, f’(у₁) = 1,

f’(x₂) = 3, f’(у₂) = 0,

f’(x₃) = 2, f’(у₃) = 0,

f’(x₄) = 1, f’(у₄) = 0.

Граф равенств, соответствующий новой допустимой вершинной разметке, изображен на рис.25. В данном случае удается построить совершенное паросочетание, которое и является оптимальным.

Контрольные вопросы и задания.

1. Постройте алгоритм нахождения максимального паросочетания двудольного графа, заданного в виде матрицы. Найдите максимальное паросочетание в графах, заданных матрицами на рис.26 и 27.

1 1 0 0 1 0 0 1 1 1 0 0 0

1 1 0 0 1 0 0 1 1 1 0 0 0

1 1 0 0 1 0 0 1 1 1 0 0 0

W₁ = 1 1 0 0 1 0 0 W₂ = 1 1 1 0 0 0

1 1 0 0 1 0 0 1 1 1 0 0 0

1 1 0 0 1 0 0 1 1 1 0 0 0

Рис. 26 Рис. 27

2. Предложите алгоритм решения следующей задачи о назначении. Пусть имеются n работников, m должностей и мера ценности работника i на должности j равна w_i,j≥0. Матрица из 0 и 1 называется насыщенной матрицей назначения, если выполняются следующие условия:

x_i,j ≤ 1,

x_i,j ≤ 1,

x_i,j = min{n,m}.

Необходимо построить насыщенную матрицу назначения, для которой x_i,j w_i,j => min.

3.Опорой двудольного графа G = (X U Y,E) называется такое подмножество вершин Q из X U Y, что каждое ребро из E имеет по крайней мере одну из концевых вершин в Q. Докажите, что минимальное число вершин в опоре двудольного графа равно максимально возможному числу ребер в паросочетании (теорема Кенига).

4. Вычислите дефицит двудольных графов, изображенных на рис.28 и 29.

○ y₁ ○ y₁

x₁ ○ x₁ ○

○ y₂ ○ y₂

x₂ ○ x₂ ○

○ y₃ ○ y₃

x₃ ○ x₃ ○

○ y₄ ○ y₄

x₄ ○ x₄ ○

○ y₅ ○ y₅

x₅ ○ x₄ ○

○ y₆

Рис. 28 Рис. 29

5. Постройте совершенное паросочетание с максимальным весом в двудольных графах, заданных матрицами весов:

3 1 4 4 6 1 5 7

1 2 2 3 2 4 9 1

W₁ = 3 4 4 5 W₂ = 4 1 1 2

2 2 1 1 5 4 2 2

6. Переформулируем задачу построения совершенного паросочетания с максимальным весом следующим образом. Найти такое подмножество элементов матрицы весов W, что

1. в каждой строке и каждом столбце находится не более одного выбранного элемента и

2. сумма выбранных элементов является наибольшей из возможных.

Подоптимальный алгоритм решения сформулированной задачи, называемый жадным [7], предполагает последовательный выбор максимальных элементов из множества X_d, допустимых для выбора элементов на k -ом шаге. Множество X_d образуют те элементы матрицы W, которые могут быть добавлены к выбранным элементам на предыдущих шагах, не нарушая первого условия. Используя жадный алгоритм, решите задачу, сформулированную в п.5.

5. Приведите пример, для которого паросочетание, найденное с помощью жадного алгоритма, не является оптимальным.

Библиографический список

1. Евстигнеев В.А. Применение теории графов в программировании. М.: Наука, 1985. 352 с.

2. Свами М., Тхуласираман К. Графы, сети и алгоритмы: Пер. с англ.- М.: Мир, 1984. 454с.

3. Кнут Д. Искусство программирования для ЭВМ. Пер. с англ. – М.: Мир, 1978. 482с.

4. Альсведе Р., Вегенер И. Задачи поиска: Пер. с англ. М.: Мир, 1982. 368с.

5. Романовский И.В. Алгоритмы решения экстремальных задач. М.: Наука, 1977. 352с.

6. Кофман А. Введение в прикладную комбинаторику. М.: Наука, 1975. 479с.

7. Липский В. Комбинаторика для программистов.: Пер. с польск. – М.: Мир, 1988, 213с.

СОДЕРЖАНИЕ

1. Основные определения теории графов..........................1

2. Кратчайшие пути..............................................................

3. Потоки в транспортной сети...........................................

4. Построение оптимальных деревьев поиска...................

5. Максимальное паросочетание в двудольном графе......

6. Библиографический список..............................................