Гамильтоновость локально связных графов

Abstract

Граф называется гамильтоновым, если в нем имеется гамильтонов цикл, т. е. простой цикл, содержащий все вершины этого графа. К проблеме гамильтоновости графов, а также к ее взвешенному аналогу – задаче о коммивояжере, проявляется устойчивый интерес в течение многих лет, а исследование этих задач представляет собой одно из магистральных направлений теории графов и комбинаторной оптимизации. Задача о гамильтоновом цикле NP-полна в общем случае [2] и остается NP-полной во многих узких классах графов. С другой стороны, известен ряд достаточных условий, когда эта задача разрешима за полиномиальное время. Исследование «областей эффективности» задачи о гамильтоновом цикле – классов графов, для которых эта задача может быть решена за полиномиальное время,– имеет не только теоретический, но и практический интерес.