Реферат: Типовой расчет графов
Первый этап - получение нулей не нужен, т. к. нули уже есть во всех строк и столбцах.
Второй этап - нахождение полного паросочетания.
| 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 |
Исходный граф
Полученный граф: