Математическое моделирование на графах. Часть 1. Берцун В.Н. - 60 стр.

UptoLike

ВУЗ: 

ТГУ | Томск

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

Рубрика: 

60 В.Н. Берцун. МАТЕМАТИЧЕСКОЕ МОДЕЛИРОВАНИЕ НА ГРАФАХ. Часть 1
В рассматриваемой задаче вес ребра c
ij
(расстояние между вер-
шинами i и j) не зависит от направления обхода, поэтому существует
только три различных гамильтоновых цикла. Если c
ij
≠ c
ji
, то такая
задача коммивояжера называется несимметричной.
Метод полного перебора неэффективен даже для сравнительно
небольших значений n, так как потребуется порядка O(n!) шагов.
Так как n! с увеличением n растет быстрее, чем любой полином от n
и даже быстрее 2
n
, то задача коммивояжера принадлежит к числу NP
– полных задач [24]. Заметим, что, например, алгоритм Гаусса реше-
ния системы из n линейных уравнений имеет полиномиальную
сложность с числом операций O(n
3
). Поэтому увеличение размерно-
сти системы в два раза увеличивает число операций на порядок.
Иначе обстоит дело с определением гамильтонова цикла методом
полного перебора. При увеличении числа вершин графа в два раза
количество операций увеличивается более, чем в 2
n
раз. Поэтому не-
гамильтоновость графа установить гораздо труднее, чем найти га-
мильтонов цикл.
Очевидно, что гамильтонов граф должен быть двусвязным, одна-
ко этого условия недостаточно.
Тэта-графом называется граф, содержащий только вершины сте-
пени 2 и две несмежные вершины степени 3.
Примеры таких двусвязных графов представлены на рис. 2.17.
Рис. 2.17
Тэта-граф негамильтонов и имеет 3 простых попарно не пересе-
кающихся цепи длины не менее двух.
Общего решения задачи о распознавании гамильтоновости гра-
фов, в отличие от эйлеровых графов, пока не найдено.

Страницы