ДОСТАТОЧНОЕ УСЛОВИЕ ОТСУТСТВИЯ ГАМИЛЬТОНОВОЙ ЦЕПИ

Введение

Теория графов моделирует реальный мир. Например, продавцам нужно перемещаться в разные места, чтобы продать их товар. Моделью для этой ситуации служит граф с вершинами, которые представляют места покупателей, и ребрами, представляющими пути, которые нужны, чтобы добраться до этих покупателей. Путь должен проходить через всех покупателей. Повторение нежелательно, так как каждому покупателю достаточно быть посещенным один раз. Решением такой задачи является цепь, которая проходит по всем вершинам один раз – гамильтонова цепь. Она всегда позволит посетить каждого покупателя единожды. Так что раз гамильтонова цепь всегда является решением, то знание того, существует ли такая цепь в графе, достаточно важно. Очень полезно было бы существование теста, проверяющего наличие гамильтоновой цепи.

Постановка проблемы

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

Основные определения

Введем некоторые определения, которые будут использованы в работе.

Определение 1. Маршрут – чередующаяся последовательность вершин и ребер, начинающаяся и заканчивающаяся вершиной, в которой любые два соседних элемента инцидентны. Путь (цепь) – маршрут, все ребра которого различны. Одна вершина также является путем. Цикл – путь в графе, в котором начальная и конечная вершины совпадают.

Определение 2. Гамильтонова цепь – цепь в графе, содержащая все вершины графа ровно по одному разу.  Гамильтонов граф – граф, содержащий гамильтонову цепь.

Определение 3. Независимое множество вершин — такое множество вершин графа G, что любые две вершины в нем не смежны, то есть никакая пара вершин не соединена ребром. Независимое множество называется максимальным, когда нет другого независимого множества, в которое оно бы входило. Число вершин в максимально независимом множестве называется числом независимости.

Определение 4. Компонента графа – некоторое подмножество вершин графа, такое, что для любых двух вершин из этого множества существует путь из одной в другую, и не существует пути из вершины этого множества в вершину не из этого множества. Одна вершина также является компонентой.

Определение 5. Точка сочленения – вершина, при удалении которой в графе увеличивается число компонент связности.

Вспомогательные теоремы

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

Лемма 1. Предположим, что k вершин были удалены из гамильтоновой цепи С. Тогда останется p несоединенных путей, таких что p £ k + 1.

Доказательство. Докажем лемму 1 с помощью метода математической индукции.

1. База индукции. Допустим k = 1 для цепи из произвольного числа вершин, как на рисунке 1(a). Тогда если k = 1, то останется 2 пути, доказывая справедливость леммы для k = 1.

Рисунок 1. Удаление одной вершины из цепи

2. Предположение индукции. Теперь предположим, что лемма 1 справедлива для k вершин. Удаляем k вершин из цепи С, порождая p несоединенных путей и p ≥ k + 1.  
3. Шаг индукции. Допуская, что лемма 1 справедлива для k вершин, докажем, что ее справедливость сохраняется и для k¢ = k + 1 вершин.

После удаления вершины из цепи C, число новых несоединенных путей p' может получится равным:

               (1)

Пусть число удалённых вершин: k' = k + 1.                                                   (2)

Согласно предположению индукции, утверждение p ≥ k + 1 верно. Тогда следующие неравенства также будут справедливы:

                                     (3)

Используя (1) и (2) доказано, что p' ≥ k' + 1.

Таким образом, допуская, что лемма 1 справедлива для k вершин, ее справедливость сохраняется и для k + 1 вершин. Лемма 1 доказана.

Пример 1. Удалим вершины из 8-вершинной цепи. Исходная цепь представлена на рисунке 2(а). При удалении вершины 5 получим граф, изображенный на рисунке 2(b), где k₁ = 1 и p₁ = 2. Следующей удалим вершину 2, соответствующий граф показан на рисунке 2(с), где k₂ = k₁ + 1 = 2 и p₂ = 3. Путь разделен на два так, что p₂ = p₁ + 1, по формуле (1). При удалении вершины 3 получим, что p₃ = p₂ = 3 и k₃ = k₂ + 1 = 3. На рисунке 2(e) удалена вершина 4, порождая две компоненты p₄ = 2 и k₄ = 4. На рисунке 2(f) вершина удаляется так, что p₅ = 2 и k₅ = 5. Далее на рисунке 2(g) p₆ = p₅ = 2 и k₆ = 6. В графе, изображенном на рисунке 2(h) p₇ = 1 и k₇ = 7. После удаления последней вершины получаем p₈ = 0 и k₈ = 8. В каждом случае неравенство p £ k + 1 из леммы 1 выполняется.

Рисунок 2. Удаление вершин из 8-вершинной цепи

Теорема 1. Пусть дан гамильтонов граф G, тогда удаление n вершин породит m несоединенных компонент, таких, что m £ n + 1.

Доказательство. Данный граф G - гамильтонов, значит, по определению 2, в нем есть гамильтонова цепь, которую обозначим как С. По лемме 1, когда мы удалим n вершин из С, останется m_С несоединенных путей, причём m_С £ n + 1. Так как пути не соединены, они являются компонентами. Если граф G содержит только ребра из цепи С и никаких других, то число компонент останется m и m = m_С, тогда теорема доказана, так как m_C £ n + 1 из чего следует m £ n + 1. Однако, если в графе G есть ребра, не входящие в гамильтонову цепь С, то эти ребра могут соединять некоторые m_С компоненты при удалении n вершин. Обозначим фактическое число компонент как m и m < m_C, так как возможное объединение компонентов уменьшает фактическое их число. Так как m £ m_C и m_C £ n + 1, то m £ n + 1. Таким образом, при удалении n вершин из графа G, число компонент будет m и m £ n + 1. Теорема доказана.

Пример 2. Рассмотрим смысл теоремы 1 на примере. Первый случай – это приложение леммы 1, он был продемонстрирован на рисунке 2. Второй случай похож на первый и продемонстрирован на рисунке 3 с гамильтоновым графом. Рисунок 3(а) - исходный гамильтонов граф. Удаляем одну вершину, порождая граф, изображенный на рисунке 3(b) с n₁ = 1 и m₁ = 1. Следующее удаление отражает рисунок 3(с), где n₂ = n₁ + 1 = 2 и m₂ = 2. Следующий рисунок 3(d) с n₃ = 3 и m₃ = 2. Граф на рисунке 3(е) имеет n₄ = 4 и m₄ = 2. Графу 3(f) соответствует n₅ = 5 и m₅ = 2. На рисунке 3(g) n₆ = 6 и m₆ = 2. При удалении следующей вершины, результат которого показан на рисунке 3(h), получаем n₇ = 7 и m₇ = 1. На рисунке 3(i) n₈ = 8 и m₈ = 0. В процессе удаления всех вершин неравенство m £ n + 1 из теоремы 1 останется справедливым.

Рисунок 3. Удаление вершин из гамильтонова графа

Заметим, что гамильтонова цепь в начальном графе 3(а) – это цепь 2(а). Также, заметим, что вершины на рисунке 3 удаляются так же, как и на рисунке 2. Ребра в исходном графе 3(а), которые не были в цикле 2(а) – единственная причина уменьшения числа компонент, которые были получены удалением вершин на рисунке 3 по сравнению с рисунком 2.

Первый достаточный признак

Теорема 2. Пусть G - такой граф, что удаление n вершин породит m несоединенных компонент, таких что m > n + 1, тогда G - негамильтонов.

Доказательство. Предположим противное, пусть исходный граф G – гамильтонов. Если G – гамильтонов, тогда удаление n вершин из G, согласно теореме 1, породит m несоединенных компонент таких что m £ n + 1. Но это утверждение противоречит условию m > n + 1. Таким образом, предположение оказалось неверно и граф G не может быть гамильтоновым. Теорема доказана.

Пример 3. Продемонстрируем работу теоремы на конкретном примере. Пусть дан граф, изображенный на рисунке 4(a) [2, с. 58].

Рисунок 4. Иллюстрация к примеру 3

Удалим вершину 8. При удалении вершины удаляются и все инцидентные ребра. Получаем граф, изображенный на рисунке 4(b). При удалении несоединенных компонент не появилось. Далее удалим вершину 12. Граф будет иметь вид как на рисунке 4(c). Число удаленных вершин n = 2, новые компоненты связности не образовались. Удалим вершину 10, получим ситуацию, изображенную на рисунке 4(d). Образовалось две компоненты связности: {13, 14, 15, 16} и {1, 2, 3, 4, 5, 6, 7, 9, 11}. Получаем n = 3, m = 2. Удалим вершину 6, рисунок 4(e). Теперь стало три компоненты связности: {13, 14, 15, 16}, {7} и {1, 2, 3, 4, 5, 9, 11}. Количество удаленных вершин n = 4, число компонент связности m = 3. Пока условие теоремы не выполняется, продолжаем удаление вершин. Удалим вершину 2, рисунок 4(f). Тогда n = 5, m = 5. Из рисунка видно, что вершины 4 и 16 инцидентны трем ребрам, то есть для появления новых компонент связности целесообразнее было бы удалить одну из них. Удалим вершину 4, получим граф, изображенный на рисунке 4(g). Теперь m = 7, n = 6. Очевидно, что для увеличения компонент связности необходимо удалить вершину 16. После её удаления граф примет вид как на рисунке 4(h). Заметим, что теперь образовалось 9 компонент связности, а количество удаленных вершин равно 7. Таким образом, m = 9, n = 7, 9 > 7 + 1. Получаем, что m > n + 1 удовлетворяет условию теоремы, доказывая, что граф на рисунке 4(a) не содержит гамильтоновой цепи.

Пример 4. Приведем ещё один пример. Пусть дан граф, изображенный на рисунке 5(a). Произведем ту же последовательность действий, как в примере 3.

Рисунок 5. Иллюстрация к примеру 4

На рисунке 4(b-f) показано последовательное удаление вершин 6, 8, 10, 12 и 14. В результате получаем, что число удаленных вершин n = 5, число компонент связности m=7, 7 > 5 + 1. Условие теоремы m > n + 1 выполняется, а это значит, что граф на рисунке 5(a) не содержит гамильтоновой цепи.

Обобщение теоремы

Отметим, что в примерах 3 и 4 удаляемые вершины выбирались таким образом, чтобы происходило максимальное увеличение компонент связности. Если бы в примере 3 были выбраны шесть смежных вершин, например, {7, 8, 9, 10, 12, 15}, то условие теоремы не было бы выполнено, так как n = 6, а m = 2 и m < n + 1. Поэтому достаточный признак, изложенный в теореме 2, не дает однозначного ответа в силу вариативности выбора удаляемых вершин. Для усиления достаточного условия отсутствия гамильтоновой цепи обобщим идею предыдущей теоремы.

Теорема 3. Пусть G – связный непустой граф, не имеющий точек сочленения, h – число вершин графа G, а a – число независимости этого графа. Тогда, если 2a > h + 1,  то граф G – негамильтонов.

Доказательство.

Предположим противное, допустим, что исходный граф G – гамильтонов.

Удалим из графа все вершины, не входящие в максимальное независимое множество. Таких вершин будет h – a. По определению, любые две вершины, входящие в независимое множество, не смежны. Таким образом, при удалении h – a вершин останется a компонент связности.

Если G – гамильтонов, тогда, согласно теореме 1, удаление h – a вершин из G породит a несоединенных компонент таких, что a £ (h – a) + 1. То есть должно выполняться неравенство 2a £ h + 1, что противоречит условию. Таким образом, предположение оказалось неверно и граф G не может быть гамильтоновым. Теорема доказана.

Пример 5. Вернемся к графу, изображенному на рисунке 4(а). Заметим, что в данном графе 16 вершин. Выберем максимально независимое множество вершин: {1, 3, 5, 7, 9, 11, 13, 14, 15}. Число независимости равно 9. 18 > 17, условие теоремы выполняется, значит, в данном графе гамильтонова цикла не существует.

Пример 6. Рассмотрим граф, изображенный на рисунке 5(а). Выберем максимально независимое множество графа {1, 3, 7, 9, 11, 13, 15, 16, 18}. Число независимости равно 9, а количество вершин 20. Условие теоремы 3 не выполняется, поэтому вопрос о существовании гамильтонова цикла в этом графе остается открытым. Но, как было показано в примере 4, с помощью теоремы 2 можно доказать, что это граф негамильтонов.

Программная реализация

На основе проведённых исследований было разработано два программных продукта, генерирующих негамильтоновы графы. Первый основан на поиске гамильтонова цикла. Во втором используется достаточный признак, представленный в работе. Пример работы первого варианта программы для 8, 10, 12, 14, 17 и 20 вершин представлен на рисунке 6.

Рисунок 6. Пример работы программы (1 вариант)

Для генерации графов без гамильтоновых путей первым способом в программе реализован алгоритм поиска с возвратом. Метод нахождения гамильтонова пути основан на алгоритме нахождения гамильтонова цикла в графе, содержащим заданное число вершин и одну дополнительную, имеющую связи со всеми остальными в графе. При вводе пользователем числа вершин n, генерируется полный связный граф на n + 1 вершинах. Реализованный алгоритм представлен в виде блок-схемы на рисунке 7.

Рисунок 7. Блок-схема генерации негамильтоновых графов (1 вариант)

На каждой итерации алгоритм пытается найти гамильтонов цикл. Если он найден, то случайным образом выбирается ребро для удаления между заданными n вершинами. Работа продолжается до тех пор, пока цикл не будет отсутствовать. Когда цикл не обнаруживается, для построения изображения графа используются исходные n вершин, со всеми оставшимися после работы алгоритма ребрами. Алгоритм поиска гамильтонова цикла можно представить блок-схемой, изображенной на рисунке 8.

Рисунок 8. Алгоритм поиска гамильтонова цикла

Второй вариант программы основывается непосредственно на достаточном признаке, изложенном в данной работе. Реализованный алгоритм представлен на рисунке 9 в виде блок-схемы.

Рисунок 9. Блок-схема генерации негамильтоновых графов (2 вариант)

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

Каждой вершине присваивается метка, что она не была посещена.

В цикле выбираем вершину и осуществляем проверку для всех соседних вершин, были ли они посещены, и если таких не находится, то текущей присваиваем метку, говорящую о том, что ее мы посетили.

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

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

Описанный выше алгоритм представлен на рисунке 10.

Рисунок 10. Алгоритм нахождения числа независимости графа

Пример работы второго варианта программы для 5, 7, 8, 10, 15 и 18 вершин представлен на рисунке 11.

Рисунок 11. Пример работы программы (2 вариант)

Результаты сравнения двух вариантов программных реализаций по производительности представлены в таблице 1.

Таблица 1.

Результаты замеров времени генерации

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

Рисунок 12.Сравнение производительности двух вариантов программных реализаций

Заключение

В данной работе нами были сформулированы и доказаны теоремы, отражающие связь между гамильтоновыми графами и компонентами связности (Лемма 1 и Теорема 1). На их основании была сформулирована и доказана достаточная теорема о несуществовании гамильтонова цикла в графе (Теорема 2) и её обобщение (Теорема 3). Стоит отметить, что данные теоремы не являются необходимыми для отсутствия гамильтоновой цепи. Все графы, показывающие, что условие не является необходимым, могут быть отнесены к негамильтоновым другими методами.

Список литературы:

1. Додонова Н.Л. Конспект лекций по дисциплине теория конечных графов и ее применения. Самара, 2010
2. Свами М., Тхуласираман К. Графы, сети и алгоритмы. М.: Мир, 1984.