Каталог@Mail.ru - каталог ресурсов интернет HitMeter - счетчик посетителей сайта, бесплатная статистика

Гамильтоновы цепи в графах. Гамильтоновы циклы

На главную Математический раздел Криптография и т.д. Новости

Гамильтонова цепь. Гамильтонов цикл. Гамильтонов граф

Перед там, как собственно разобраться с темой, напомним пару важных понятий. Простая цепь в графе - цепь, содержащая каждую вершину графа не более одного раза. Простой цикл похож по определению, но одну вершина содержится в замкнутой цепи дважды - это та, от которой мы начали "движение" и куда "вернулись". Приведём небольшой пример:

Заметим, что данные понятия важны в задачах поиска путей в графе, если наш "маршрут" не являются простой цепью либо простым циклом, то он заведомо "избыточный".

Гамильтонова цепь - простая цепь, содержащая каждую вершину графа ровно один раз. Гамильтонов цикл - простой цикл, охвативший все вершины графа. Граф, где можно составить гамильтонову цепь, называется полугамильтоновым графом. Граф, где можно составить гамильтонов цикл, называется гамильтоновым графом. Всякий гамильтонов граф является полугамильтоновым графом (убираем одно ребро из гамильтонова цикла, чтобы "разомкнуть" путь, и получаем гамильтонову цепь). Полугамильтонов граф может и не быть гамильтоновым графом.

Некоторые графы может вовсе не содержать гамильтоновых цепей и циклов, как например, граф на рис. 3. В некоторых графах гамильтоновы цепи можно составить многими способами, как например, в полных графах (графах, где каждая вершина связана рёбрами с каждой из остальных - см. рис. 4).

Наверное, важнейшей задачей, связанной с гамильтоновым циклом, является задача коммивояжёра, которая состоит в обходе всех вершин взвешенного графа с достижением минимальной суммы весов (объезде всех городов страны или региона с минимальной затратой на дороги с возвратом в пункт выезда).

Один из способов программного поиска гамильтоновых циклов - перебор с возвратом. Идея состоит в том, чтобы, навав с простейшего частичного решения (две вершины - всегда образуют простую цепь), последовательно расширять частичное решение. В данном случае частичное решение - простая цепь, поскольку подмножеством гамильтоного цикла является именно она. В ходе поиска может быть одна из двух ситуаций. 1. Получено "правильное" решение - ура, победили. 2. Частичное решение не удаётся расширить - "отступаем" на шаг, пытаясь пойти в другую сторону. Если и теперь не получается, "отступаем" дальше. Если и при отходе к стартовой вершине (с которой начали поиск) не остаётся ещё не проверенных направлений, то гамильтоновых циклов нету.

Некоторые свойства, связанные с гамильтоновыми графами

Теперь приведём ряд свойств и методов, связанных с гамильтоновыми графами.

1. Визуальное обнаружение. Если граф несвязный ("распавшийся на части") или хотя бы одна из вершин имеет степень 1, то гамильтонова цикла точно нет. Это удобно при проверке вручную, а вот при программной не так всё просто, поскольку требует отдельных алгоритмов.

2. Проверка степеней вершин по условию Дирака. Если степень вершины каждого графа не меньше половины числа вершин, граф является гамильтоновым. Если же степени не удовлетворяют условию, вопрос открыт. Например, если выпуклый n-угольник, в котором НЕ проведены диагонали, рассматривать как граф, то получим гамильтонов граф, хотя при n>4 условие нарушается (все степени равны 2).

3. Условие Оре: если сумма степеней любых двух несмежных вершин в графе не меньше числа вершин в графе, то граф является гамильтоновым. Аналогично условию Дирака при невыполнении требования к сумме степеней вопрос открыт.

4. Теорема Бонди-Хватала. Все пары несмежных вершин, сумма степеней которых не меньше числа вершин графа, соединяем ребром. Полученный граф называется замыканием исходного графа. Граф является гамильтоновым графом тогда и только тогда, когда его замыкание есть гамильтонов граф.

5. Малое число рёбер. Граф, у которого число рёбер меньше числа вершин, не может быть гамильтоновым.

6. Малая сумма степеней вершин. Если сумма степеней вершин графа меньше удвоенного числа вершин, перед нами точно не гамильтонов граф.

copyright © Исканцев Н.В., 2014

К математическому разделу
На главную
X