Линейный алгоритм построения гамильтонова цикла в локально связном графе треугольной решетки

Abstract

An efficient linear time and space algorithm for finding a hamiltonian cycle in a locally connected triangular grid graph is presented. = Исследуются конечные порожденные подграфы решетки – графы решетки, которые находят многочисленные практические применения в компьютерной графике, вычислительной геометрии и робототехнике, в теории распознавания образов, молекулярной биологии. Изучаются циклические свойства связных локально связных графов треугольной решетки. Приводится новое доказательство того, что все такие графы (за исключением одного) являются гамильтоновыми. На основе данного доказательства описывается эффективный линейный по времени и памяти алгоритм нахождения гамильтонова цикла в рассматриваемом классе графов.