Программная реализация. 
Достаточное условие отсутствия гамильтоновой цепи

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Таблица 1.

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

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

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