Типовой расчет графов (стр. 3 из 4)
| 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.
Задача 11 Решить задачу 10, используя алгоритм ветвей и границ (отождествив вершины xi и yj).
Таблица Е (исходная). Строки - xi , столбцы - yj. å=0
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 2 | 01 | 03 | 02 | 02 |
| 2 | 06 | 7 | 9 | 8 | 6 |
| 3 | 01 | 1 | 3 | 2 | 2 |
| 4 | 04 | 8 | 7 | 6 | 4 |
| 5 | 03 | 7 | 6 | 8 | 3 |
Дробим по переходу x2 - y1:
Таблица Е21 å=0+8=8
| 2 | 3 | 4 | 5 | ||
| 1 | 00 | 02 | 01 | 00 | |
| 3 | 01 | 2 | 1 | 1 | 1 |
| 4 | 4 | 3 | 2 | 02 | 4 |
| 5 | 4 | 3 | 5 | 03 | 3 |
Таблица
21 å=0+6=6 | 1 | 2 | 3 | 4 | 5 | ||
| 1 | 2 | 01 | 03 | 02 | 00 | |
| 2 | ¥ | 1 | 3 | 2 | 01 | 6 |
| 3 | 01 | 1 | 3 | 2 | 2 | |
| 4 | 04 | 8 | 7 | 6 | 4 | |
| 5 | 03 | 7 | 6 | 8 | 3 |
Продолжаем по
21:Дробим по переходу x4 - y1:
Таблица
21Е41 å=6+4=10 | 2 | 3 | 4 | 5 | ||
| 1 | 00 | 02 | 01 | 00 | |
| 2 | 1 | 3 | 2 | 01 | |
| 3 | 01 | 2 | 1 | 1 | 1 |
| 5 | 4 | 3 | 5 | 03 | 3 |
Таблица
21 41 å=6+4=10 | 1 | 2 | 3 | 4 | 5 | ||
| 1 | 2 | 01 | 03 | 02 | 00 | |
| 2 | ¥ | 1 | 3 | 2 | 01 | |
| 3 | 01 | 1 | 3 | 2 | 2 | |
| 4 | ¥ | 4 | 3 | 2 | 02 | 4 |
| 5 | 03 | 7 | 6 | 8 | 3 |
Продолжаем по Е21:
Дробим по переходу x5 - y5:
Таблица Е21Е55 å=8+2=10
| 2 | 3 | 4 | ||
| 1 | 00 | 01 | 00 | |
| 3 | 01 | 2 | 1 | |
| 4 | 2 | 1 | 01 | 2 |
Таблица Е21
55 å=8+3=11 | 2 | 3 | 4 | 5 | ||
| 1 | 00 | 02 | 01 | 00 | |
| 3 | 01 | 2 | 1 | 1 | |
| 4 | 4 | 3 | 2 | 02 | |
| 5 | 1 | 01 | 2 | ¥ | 3 |
Продолжаем по Е21Е55:
Дробим по переходу x3 - y2:
Таблица Е21Е55Е32 å=10+0=10
| 3 | 4 | |
| 1 | 01 | 00 |
| 4 | 1 | 01 |
Далее решение очевидно: x1 - y3 и x4 - y4. Это не увеличит оценку.