О графе многогранника пирамидальных циклов
DOI:
https://doi.org/10.1134/S1990478918010027Ключевые слова:
пирамидальный цикл, полиэдральный граф, необходимое и достаточное условие смежности, плотность графа, диаметр графа.Аннотация
Исследуются свойства полиэдрального графа многогранника пирамидальных циклов. Гамильтонов цикл называется пирамидальным, если коммивояжёр начинает путь в городе с номером 1, посещает некоторые города в порядке возрастания номеров, достигает города n и возвращается в исходный, проходя все оставшиеся города в порядке убывания номеров. Многогранник PYR(n) определяется как выпуклая оболочка характеристических векторов всех пирамидальных циклов в полном графе Kn. Объектом исследования выступает полиэдральный граф многогранника пирамидальных циклов, вершинами которого являются вершины многогранника, а рёбрами — геометрические рёбра, т. е. одномерные грани. Описано необходимое и достаточное условие смежности вершин многогранника PYR(n). На его основе разработан алгоритм проверки смежности с линейной трудоёмкостью. Установлено, что диаметр полиэдрального графа PYR(n) равен 2. Найдено асимптотически точное значение Θ(n2) плотности, или кликового числа, полиэдрального графа многогранника пирамидальных циклов. Известно, что данная величина характеризует временную сложность задачи в классе алгоритмов прямого типа, основанных на линейных сравнениях.
