Научная электронная библиотека

Монографии, изданные в издательстве Российской Академии Естествознания

Дискретная оптимизация и моделирование в условиях неопределенности данных

Перепелица В. А., Тебуева Ф. Б.,

3.7.1. К вопросу о критерии распознавания гамильтонова графа

На примере задачи коммивояжера можно проанализировать алгоритмическую проблему решения NP-трудных задач. Если на ориентированном (неориентированном) - вершинном графе контур (цикл) проходит через все  вершины, причем, только по одному разу, то этот контур (цикл) называется гамильтоновым. Гамильтоновым называют также граф, содержащий этот контур (цикл). Критерий существования Эйлеровых циклов является простым (теорема 3.5). Для гамильтоновых же циклов (контуров) никакого общего критерия существования не известно, т.е. не известно условие, которое бы являлось необходимым и достаточным для существования гамильтонова цикла (контура) в данном графе. Иными словами, остается еще нерешенной задача нахождения простого и эффективного описания гамильтоновых графов, которое бы отличалось от завуалированной перефразировки определения. Более того, иногда даже для конкретных графов бывает очень трудно решить, можно ли найти такой цикл.