Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Курсовая работа - Решение задачи коммивояжера - файл 1.4 стр9.doc


Курсовая работа - Решение задачи коммивояжера
скачать (194.4 kb.)

Доступные файлы (21):

1.1, 1.2 стр5.doc34kb.20.01.2009 14:21скачать
1.1 стр4.doc32kb.26.12.2005 12:31скачать
1.2 стр6.doc27kb.20.01.2009 14:23скачать
1.2 стр7.doc25kb.20.01.2009 14:23скачать
1.3 стр8.doc54kb.20.01.2009 14:24скачать
1.4 стр9.doc27kb.20.01.2009 14:25скачать
1.6 стр15.doc33kb.20.01.2009 14:27скачать
1.6 стр16.doc30kb.20.01.2009 14:26скачать
2.2, 2.1, 2.2, 2.3 стр19.doc322kb.01.06.2009 20:20скачать
2.4 стр20.doc33kb.01.06.2009 20:19скачать
2.4 стр21.doc25kb.20.01.2009 14:16скачать
2.5 стр22.doc25kb.20.01.2009 14:16скачать
2.5 стр23.doc25kb.20.01.2009 14:16скачать
2.5 стр24.doc25kb.20.01.2009 14:16скачать
2.5 стр25.doc23kb.20.01.2009 14:16скачать
Введение стр2.doc35kb.20.01.2009 14:17скачать
Введение стр3.doc24kb.20.01.2009 14:17скачать
Заключение стр24.doc24kb.20.01.2009 14:18скачать
Лист задания.doc33kb.07.12.2004 11:35скачать
Литература стр26.doc25kb.20.01.2009 14:19скачать
Приложение стр25.doc48kb.20.01.2009 14:19скачать

1.4 стр9.doc



1.4 Условия существования Гамильтонова контура
Последовательность (путь), который требуется найти – ориентированный остовный простой цикл минимального веса в орграфе; такие циклы также называют гамильтоновыми. Очевидно, что в полном орграфе циклы указанного выше типа есть. Заметим, что вопрос о наличии в орграфе гамильтонова цикла достаточно рассмотреть как частный случай задачи о коммивояжере для полных орграфов. Действительно, если данный орграф не является полным, то его можно дополнить до полного недостающими ребрами и каждому из добавленных ребер приписать вес - это «компьютерная бесконечность», т.е. максимальное из всех возможных в рассмотрениях чисел. Если во вновь построенном полном орграфе найти теперь легчайший гамильтонов цикл, то при наличии у него ребер с весом можно будет говорить, что в данном, исходном графе «цикла коммивояжера» нет. Если же в полном орграфе легчайший гамильтонов цикл окажется конечным по весу, то он и будет искомым циклом в исходном графе. Гамильтоновым контуром называется путь, проходящий через все вершины графа, у которого начальная вершина совпадает с конечной. Здесь под длиной контура понимают не количество дуг, входящих в контур, а сумму их длин.

Цикл Гамильтона.

Пусть G-граф. Циклом Гамильтона называется простой цикл, который содержит все вершины данного графа.

Теорема 1.

Для того, чтобы в графе существовал цикл Гамильтона, необходимо, чтобы этот граф был связным.

Теорема 2.

В полном графе , если n>=3, цикл Гамильтона есть в полном двудольном при m>=1, цикл Гамильтона есть.

2301055905000ПЗ


Лист

Дата

Подпись

№ документа

Лист

Изм.

9



Скачать файл (194.4 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации