Реферат: Типовой расчет графов
--PAGE_BREAK--Дробим по переходу x2-x3:
--PAGE_BREAK--
Таблица <img width=«13» height=«15» src=«ref-1_824274416-90.coolpic» v:shapes="_x0000_i1066">23<img width=«13» height=«15» src=«ref-1_824274416-90.coolpic» v:shapes="_x0000_i1067">36<img width=«13» height=«15» src=«ref-1_824274416-90.coolpic» v:shapes="_x0000_i1068">45<img width=«13» height=«19» src=«ref-1_824274506-95.coolpic» v:shapes="_x0000_i1069">51 å=14+6=20
x1
x2
x4
x1
¥
1
01
x5
¥
01
¥
x6
¥
00
6
Окончательно имеем Гамильтонов контур: 2,3,6,4,5,1,2.
<img width=«291» height=«316» src=«ref-1_824276596-1655.coolpic» v:shapes="_x0000_i1070">
Прадерево разбиений:
<img width=«358» height=«339» src=«ref-1_824278251-2571.coolpic» v:shapes="_x0000_i1071">
Задача 10 (Задача о назначениях) Дан полный двудольный граф Knn с вершинами первой доли x1, x2,...xn.и вершинами другой доли y1, y2,...yn… Вес ребра {xi,yj} задается элементами vij матрицы весов. Используя венгерский алгоритм, найти совершенное паросочетание минимального (максимального веса). Выполнить рисунок.
Матрица весов двудольного графа K55 :
y1
y2
y3
y4
y5
x1
2
x2
7
9
8
6
x3
1
3
2
2
x4
8
7
6
4
x5
7
6
8
3
Первый этап — получение нулей не нужен, т. к. нули уже есть во всех строк и столбцах.
Второй этап — нахождение полного паросочетания.
y1
y2
y3
y4
y5
x1
2
x2
7
9
8
6
x3
1
3
2
2
x4
8
7
6
4
x5
7
6
8
3
Третий этап — нахождение максимального паросочетания.
y1
y2
y3
y4
y5
x1
2
X
x2
7
9
8
6
X
x3
1
3
2
2
x4
8
7
6
4
x5
7
6
8
3
X
X
Четвертый этап — нахождение минимальной опоры.
y1
y2
y3
y4
y5
x1
2
x2
7
9
8
6
5
x3
1
3
2
2
1
x4
8
7
6
4
2
x5
7
6
8
3
3
4
Пятый этап — возможная перестановка некоторых нулей.
y1
y2
y3
y4
y5
x1
3
x2
6
8
7
5
5
x3
2
1
1
1
x4
7
6
5
3
2
x5
6
5
7
2
3
4
Решение с ненулевым значением. Переход ко второму этапу.
Полное паросочетание:
y1
y2
y3
y4
y5
x1
3
x2
6
8
7
5
x3
2
1
1
x4
7
6
5
3
x5
6
5
7
2
Максимальное паросочетание:
y1
y2
y3
y4
y5
x1
3
X
x2
6
8
7
5
X
x3
2
1
1
x4
7
6
5
3
x5
6
5
7
2
X
X
продолжение
--PAGE_BREAK--
Минимальная опора:
y1
y2
y3
y4
y5
x1
3
6
x2
6
8
7
5
7
x3
2
1
1
1
x4
7
6
5
3
2
x5
6
5
7
2
3
4
5
Перестановка нулей:
y1
y2
y3
y4
y5
x1
3
6
x2
6
8
7
5
7
x3
2
1
1
1
x4
7
6
5
3
2
x5
6
5
7
2
3
4
5
Полное паросочетание:
y1
y2
y3
y4
y5
x1
3
6
x2
6
8
7
5
7
x3
2
1
1
1
x4
7
6
5
3
2
x5
6
5
7
2
3
4
5
Максимальное паросочетание:
y1
y2
y3
y4
y5
x1
3
X
x2
6
8
7
5
x3
2
1
1
X
x4
7
6
5
3
X
x5
6
5
7
2
X
X
X
Минимальная опора:
y1
y2
y3
y4
y5
x1
3
x2
6
8
7
5
1
x3
2
1
1
x4
7
6
5
3
x5
6
5
7
2
2
3
Перестановка нулей:
y1
y2
y3
y4
y5
x1
5
x2
4
6
5
3
1
x3
2
2
1
1
x4
2
7
6
5
3
x5
4
3
5
2
3
Полное паросочетание:
y1
y2
y3
y4
y5
x1
5
x2
4
6
5
3
x3
2
2
1
1
x4
2
7
6
5
3
x5
4
3
5
Максимальное паросочетание:
y1
y2
y3
y4
y5
x1
5
X
x2
4
6
5
3
X
x3
2
2
1
1
X
x4
2
7
6
5
3
x5
4
3
5
X
X
X
X
X
Минимальная опора:
y1
y2
y3
y4
y5
x1
5
x2
4
6
5
3
x3
2
2
1
1
x4
2
7
6
5
3
1
x5
4
3
5
продолжение
--PAGE_BREAK--
Перестановка нулей:
y1
y2
y3
y4
y5
x1
5
x2
4
6
5
3
x3
2
2
1
1
x4
5
4
3
1
1
x5
4
3
5
Полное паросочетание:
y1
y2
y3
y4
y5
x1
5
x2
4
6
5
3
x3
2
2
1
1
x4
5
4
3
1
1
x5
4
3
5
Максимальное паросочетание:
y1
y2
y3
y4
y5
x1
5
X
x2
4
6
5
3
X
x3
2
2
1
1
X
x4
5
4
3
1
x5
4
3
5
X
X
X
X
X
Минимальная опора:
y1
y2
y3
y4
y5
x1
5
x2
4
6
5
3
3
x3
2
2
1
1
x4
5
4
3
1
1
x5
4
3
5
2
Перестановка нулей:
y1
y2
y3
y4
y5
x1
6
x2
3
5
4
2
3
x3
3
2
1
1
x4
4
3
2
1
x5
1
4
3
5
2
Полное паросочетание:
y1
y2
y3
y4
y5
x1
6
x2
3
5
4
2
3
x3
3
2
1
1
x4
4
3
2
1
x5
1
4
3
5
2
Максимальное паросочетание:
y1
y2
y3
y4
y5
x1
6
X
x2
3
5
4
2
X
x3
3
2
1
1
X
x4
4
3
2
x5
1
4
3
5
X
X
X
X
X
Минимальная опора:
y1
y2
y3
y4
y5
x1
6
x2
3
5
4
2
4
x3
3
2
1
1
x4
4
3
2
1
x5
1
4
3
5
5
2
3
продолжение
--PAGE_BREAK--
еще рефераты
Еще работы по математике
Реферат по математике
Решение военно-логической задачи по распределению ударной группы авиационного подразделения
3 Сентября 2013
Реферат по математике
Математические основы теории систем 2
3 Сентября 2013
Реферат по математике
Призма 2
20 Июня 2015
Реферат по математике
Модификация метода построения тестов для конечных автоматов относительно неразделимости
3 Сентября 2013