Типовой расчет графов - (реферат)
p>б) Гамильтонов цикл (ребра с измененной ориентацией показаны пунктиром):Задача 9 (Задача о коммивояжере) Дан полный ориентированный симметрический граф с вершинами x1, x2, ....xn. Вес дуги xixj задан элементами Vijматрицы весов. Используя алгоритм метода ветвей и границ, найти Гамильтонов контур минимального (максимального) веса. Задачу на максимальное значение Гамильтонова контура свести к задаче на минимальное значение, рассмотрев матрицу с элементами, где . Выполнить рисунок.
Исходная таблица.
x1
x2
x3
x4
x5
x6
x1
Ґ
3
7
2
Ґ
11
x2
8
Ґ
06
Ґ
4
3
x3
6
05
Ґ
7
Ґ
2
x4
6
Ґ
13
Ґ
5
Ґ
x5
3
3
3
4
Ґ
5
x6
8
6
Ґ
2
2
Ґ
Таблица Е 14
x1
x2
x3
x4
x5
x6
x1
Ґ
1
5
01
Ґ
7
2
x2
8
Ґ
01
Ґ
4
1
x3
6
00
Ґ
7
Ґ
00
x4
1
Ґ
8
Ґ
01
Ґ
5
x5
01
00
00
1
Ґ
00
3
x6
6
4
Ґ
00
00
Ґ
2
2
Дробим по переходу x2-x3:
Таблица 23 е=14+0=14
x1
x2
x4
x5
x6
x1
Ґ
1
01
Ґ
7
x3
6
Ґ
7
Ґ
06
x4
1
Ґ
Ґ
01
Ґ
x5
01
01
1
Ґ
00
x6
6
4
00
00
Ґ
Таблица 23 е=14+1=15
x1
x2
x3
x4
x5
x6
x1
Ґ
1
5
01
Ґ
7
x2
7
Ґ
Ґ
Ґ
3
03
1
x3
6
00
Ґ
7
Ґ
00
x4
1
Ґ
8
Ґ
01
Ґ
x5
01
00
05
1
Ґ
00
x6
6
4
Ґ
00
00
Ґ
Продолжаем по 23. Дробим по переходу x3-x6:
Таблица 23E36 е=14+0=14
x1
x2
x4
x5
x1
Ґ
1
01
Ґ
x4
1
Ґ
Ґ
01
x5
01
01
1
Ґ
x6
6
Ґ
00
00
Таблица 2336 е=14+6=20
x1
x2
x4
x5
x6
x1
Ґ
1
01
Ґ
7
x3
01
Ґ
1
Ґ
Ґ
6
x4
1
Ґ
Ґ
01
Ґ
x5
00
01
1
Ґ
07
x6
6
4
00
00
Ґ
Продолжаем по 2336. Дробим по переходу x4-x5:
Таблица 23E3645 е=14+0=14
x1
x2
x4
x1
Ґ
1
01
x5
01
01
1
x6
6
Ґ
00
Таблица 233645 е=14+1=15
x1
x2
x4
x5
x1
Ґ
1
01
Ґ
x4
00
Ґ
Ґ
Ґ
1
x5
01
01
1
Ґ
x6
6
Ґ
00
00
Продолжаем по 233645. Дробим по переходу x5-x1:
Таблица 23364551 е=14+1=15
x2
x4
x1
1
Ґ
1
x6
Ґ
00
Таблица 23364551 е=14+6=20
x1
x2
x4
x1
Ґ
1
01
x5
Ґ
01
Ґ
x6
0
Ґ
00
6
Окончательно имеем Гамильтонов контур: 2, 3, 6, 4, 5, 1, 2.
Прадерево разбиений:
