Элементарные решения неэлементарных задач на графах. Берзин Е.А. - 43 стр.

UptoLike

ВУЗ: 

ТвГТУ | Тверь

Составители: 

Рубрика: 

45
Таблица 17. Совмещенная матрица КМ
0
0
kj
kj
L
μ
j
k
1 2 3 4 5 6
1
13
1,3,6,4,1
9
2,6,4,1
8
3,6,4,1
3
4;1
6
)5,4(5,4,1
5
6,4,1
2
11
1,3,2
15
2,6,4,3,2
20
3;2
9
4,3,2
12
5,4,3,2
11
6,4,3,2
3
5
1;3
9
2,6,4,3
8
3,6,4,3
3
4;3
6
5,4,3
5
6,4,3
4
10
1,3,6,4
6
2,6,4
5
3,6,4
8
4,3,6,4
3
5;4
2
6;4
5
17
31,2,5
6
2;5
12
3,2,5
15
4,3,2,5
18
5,4,3,2,5
17
6,4,3,2,5
6
8
1,3,6
4
2;6
3
3;6
6
4,3,6
9
5,4,3,6
8
6,4,3,6
Если в качестве начального цикла взять любой оптимальный
неполный цикл (главная диагональ табл. 9), то также будут получены
оптимальные решения, при этом решение (3.12) не является единственным,
например:
311,3,6,4,3,2,5,1
=
L .
Решение задачи при
1<
ϕ
существует, если матрица
ij
c=c является
сильно связной. Необходимым и достаточным условием сильносвязности
матрицы является возможность построения хотя бы одного гамильтонова
цикла. Такой цикл возможен, если из матрицы с может быть выделена
подматрица, содержащая по одному элементу с
ij
в каждой строке и каждом
столбце, при этом ни одна пара элементов не является симметричной
относительно главной диагонали. Полная матрица кратчайших маршрутов
не существует, если матрица с не является сильно связной.
Выводы
1. При полной (1=
ϕ
) матрице смежности с (матрице расстояний)
для решения задачи определения гамильтонова цикла на графе наиболее
целесообразно использовать метод расширения цикла (рис. 3). В качестве

Страницы