О графе многогранника пирамидальных циклов

Исследуются свойства полиэдрального графа многогранника пирамидальных циклов. Гамильтонов цикл называется пирамидальным, если коммивояжёр начинает путь в городе с номером $1$, посещает некоторые города в порядке возрастания номеров, достигает города $n$ и возвращается в исходный, проходя все оставшиеся города в порядке убывания номеров. Многогранник $\mathrm{PYR}(n)$ определяется как выпуклая оболочка характеристических векторов всех пирамидальных циклов в полном графе $K_n$. Объектом исследования выступает полиэдральный граф многогранника пирамидальных циклов, вершинами которого являются вершины многогранника, а рёбрами – геометрические рёбра, т.е. одномерные грани. Описано необходимое и достаточное условие смежности вершин многогранника $\mathrm{PYR}(n)$. На его основе разработан алгоритм проверки смежности с линейной трудоёмкостью. Установлено, что диаметр полиэдрального графа $\mathrm{PYR}(n)$ равен $2$. Найдено асимптотически точное значение $\Theta(n^2)$ плотности, или кликового числа, полиэдрального графа многогранника пирамидальных циклов. Известно, что данная величина характеризует временную сложность задачи в классе алгоритмов прямого типа, основанных на линейных сравнениях. Ил. 4, библиогр. 23.