Типовой расчет графов - (реферат)
p>Задача 10 (Задача о назначениях) Дан полный двудольный граф Knn с вершинами первой доли x1, x2, ....xn. и вершинами другой доли y1, y2, ....yn...Вес ребра {xi, yj} задается элементами vijматрицы весов. Используя венгерский алгоритм, найти совершенное паросочетание минимального (максимального веса). Выполнить рисунок.Матрица весов двудольного графа K55 :
y1
y2
y3
y4
y5
x1
2
0
0
0
0
x2
0
7
9
8
6
x3
0
1
3
2
2
x4
0
8
7
6
4
x5
0
7
6
8
3
Первый этап - получение нулей не нужен, т. к. нули уже есть во всех строк и столбцах.
Второй этап - нахождение полного паросочетания.
y1
y2
y3
y4
y5
x1
2
0
0
0
0
x2
0
7
9
8
6
x3
0
1
3
2
2
x4
0
8
7
6
4
x5
0
7
6
8
3
Третий этап - нахождение максимального паросочетания.
y1
y2
y3
y4
y5
x1
2
0
0
0
0
X
x2
0
7
9
8
6
X
x3
0
1
3
2
2
x4
0
8
7
6
4
x5
0
7
6
8
3
X
X
Четвертый этап - нахождение минимальной опоры.
y1
y2
y3
y4
y5
x1
2
0
0
0
0
x2
0
7
9
8
6
5
x3
0
1
3
2
2
1
x4
0
8
7
6
4
2
x5
0
7
6
8
3
3
4
Пятый этап - возможная перестановка некоторых нулей.
y1
y2
y3
y4
y5
x1
3
0
0
0
0
x2
0
6
8
7
5
5
x3
0
0
2
1
1
1
x4
0
7
6
5
3
2
x5
0
6
5
7
2
3
4
Решение с ненулевым значением. Переход ко второму этапу.
Полное паросочетание:
y1
y2
y3
y4
y5
x1
3
0
0
0
0
x2
0
6
8
7
5
x3
0
0
2
1
1
x4
0
7
6
5
3
x5
0
6
5
7
2
Максимальное паросочетание:
y1
y2
y3
y4
y5
x1
3
0
0
0
0
X
x2
0
6
8
7
5
X
x3
0
0
2
1
1
x4
0
7
6
5
3
x5
0
6
5
7
2
X
X
Минимальная опора:
y1
y2
y3
y4
y5
x1
3
0
0
0
0
6
x2
0
6
8
7
5
7
x3
0
0
2
1
1
1
x4
0
7
6
5
3
2
x5
0
6
5
7
2
3
4
5
Перестановка нулей:
y1
y2
y3
y4
y5
x1
3
0
0
0
0
6
x2
0
6
8
7
5
7
x3
0
0
2
1
1
1
x4
0
7
6
5
3
2
x5
0
6
5
7
2
3
4
5
Полное паросочетание:
y1
y2
y3
y4
y5
x1
3
0
0
0
0
6
x2
0
6
8
7
5
7
x3
0
0
2
1
1
1
x4
0
7
6
5
3
2
x5
0
6
5
7
2
3
4
5
Максимальное паросочетание:
y1
y2
y3
y4
y5
x1
3
0
0
0
0
X
x2
0
6
8
7
5
x3
0
0
2
1
1
X
x4
0
7
6
5
3
X
x5
0
6
5
7
2
X
X
X
Минимальная опора:
y1
y2
y3
y4
y5
x1
3
0
0
0
0
x2
0
6
8
7
5
1
x3
0
0
2
1
1
x4
0
7
6
5
3
x5
0
6
5
7
2
2
3
Перестановка нулей:
y1
y2
y3
y4
y5
x1
5
0
0
0
0
x2
0
4
6
5
3
1
x3
2
0
2
1
1
x4
2
7
6
5
3
x5
0
4
3
5
0
2
3
Полное паросочетание:
y1
y2
y3
y4
y5
x1
5
0
0
0
0
x2
0
4
6
5
3
x3
2
0
2
1
1
x4
2
7
6
5
3
x5
0
4
3
5
0
Максимальное паросочетание:
y1
y2
y3
y4
y5
x1
5
0
0
0
0
X
x2
0
4
6
5
3
X
x3
2
0
2
1
1
X
x4
2
7
6
5
3
x5
0
4
3
5
0
X
X
X
X
X
Минимальная опора:
y1
y2
y3
y4
y5
x1
5
0
0
0
0
x2
0
4
6
5
3
x3
2
0
2
1
1
x4
2
7
6
5
3
1
x5
0
4
3
5
0
Перестановка нулей:
y1
y2
y3
y4
y5
x1
5
0
0
0
0
x2
0
4
6
5
3
x3
2
0
2
1
1
x4
0
5
4
3
1
1
x5
0
4
3
5
0
Полное паросочетание:
y1
y2
y3
y4
y5
x1
5
0
0
0
0
x2
0
4
6
5
3
x3
2
0
2
1
1
x4
0
5
4
3
1
1
x5
0
4
3
5
0
Максимальное паросочетание:
y1
y2
y3
y4
y5
x1
5
0
0
0
0
X
x2
0
4
6
5
3
X
x3
2
0
2
1
1
X
x4
0
5
4
3
1
x5
0
4
3
5
0
X
X
X
X
X
Минимальная опора:
y1
y2
y3
y4
y5
x1
5
0
0
0
0
x2
0
4
6
5
3
3
x3
2
0
2
1
1
x4
0
5
4
3
1
1
x5
0
4
3
5
0
2
Перестановка нулей:
y1
y2
y3
y4
y5
x1
6
0
0
0
0
x2
0
3
5
4
2
3
x3
3
0
2
1
1
x4
0
4
3
2
0
1
x5
1
4
3
5
0
2
Полное паросочетание:
y1
y2
y3
y4
y5
x1
6
0
0
0
0
x2
0
3
5
4
2
3
x3
3
0
2
1
1
x4
0
4
3
2
0
1
x5
1
4
3
5
0
2
Максимальное паросочетание:
y1
y2
y3
y4
y5
x1
6
0
0
0
0
X
x2
0
3
5
4
2
X
x3
3
0
2
1
1
X
x4
0
4
3
2
0
x5
1
4
3
5
0
X
X
X
X
X
Минимальная опора:
y1
y2
y3
y4
y5
x1
6
0
0
0
0
x2
0
3
5
4
2
4
x3
3
0
2
1
1
x4
0
4
3
2
0
1
x5
1
4
3
5
0
5
2
3
В результате имеем:
y1
y2
y3
y4
y5
x1
6
0
0
0
0
x2
0
1
3
2
2
4
x3
3
0
2
1
1
x4
0
2
1
0
0
1
x5
1
4
3
5
0
5
2
3
Исходный граф
Полученный граф:
Вес найденного совершенного паросочетания = 12.
