Том 25, номер 1, 2018 г., Стр. 5-24

УДК 519.16+514.172.45
Бондаренко В. А., Николаев А. В.
О графе многогранника пирамидальных циклов

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

Ключевые слова: пирамидальный цикл, полиэдральный граф, необходимое и достаточное условие смежности, плотность графа, диаметр графа.

DOI: 10.17377/daio.2018.25.570

Бондаренко Владимир Александрович ¹
Николаев Андрей Валерьевич ¹
1. Ярославский гос. университет им. П. Г. Демидова,
ул. Советская, 14, 150003, Ярославль, Россия
е-mail: bond@bond.edu.yar.ru, andrei.v.nikolaev@gmail.com

Статья поступила 3 марта 2017 г.

Литература

[1] Айзенштат В. С., Кравчук Д. Н. О минимуме линейной формы на множестве всех полных циклов симметрической группы $S_n$ // Кибернетика. 1968. № 2. С. 64–66.

[2] Белов Ю. А. О плотности графа матроида // Модели исследования операций в вычислительных системах. Ярославль, 1985. С. 95–100.

[3] Бондаренко В. А. Неполиномиальная нижняя оценка сложности задачи коммивояжёра в одном классе алгоритмов // Автоматика и телемеханика. 1983. № 9. C. 45–50.

[4] Бондаренко В. А., Максименко А. Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 c.

[5] Бондаренко В. А., Николаев А. В., Шовгенов Д. А. Полиэдральные графы задач об остовных деревьях при дополнительных ограничениях // Моделирование и анализ информационных систем. 2015. T. 22, № 4. C. 453–463.

[6] Кляус П. С. Обобщение тестовых задач для задачи коммивояжёра // Препринт № 16, Ин-т математики АН БССР, Минск, 1976.

[7] Applegate D. L., Bixby R. E., Chvátal V., Cook W. J. The traveling salesman problem: a computational study. Princeton, NJ: Princeton Univ. Press, 2007. 608 p.

[8] Bondarenko V. A., Nikolaev A. V. On graphs of the cone decompositions for the min-cut and max-cut problems // Int. J. Math. Math. Sci. 2016. Vol. 2016. P. 1–6.

[9] Bondarenko V. A., Nikolaev A. V. On the skeleton of the pyramidal tours polytope // Abstr. 17th Baikal Int. School - Seminar “Methods of Optimization and Their Applications”. Irkutsk: ESI SB RAS, 2017. P. 84.

[10] Bondarenko V. A., Nikolaev A. V. Some properties of the skeleton of the pyramidal tours polytope // Electron. Notes Discrete Math. 2017. Vol. 61. P. 131–137.

[11] Burkard R. E., Deineko V. G., Van Dal R., Van der Veen J. A. A., Woeginger G. J. Well-solvable special cases of the traveling salesman problem: a survey // SIAM Rev. 1998. Vol. 40, No. 3. P. 496–546.

[12] Dantzig G., Fulkerson R., Johnson S. Solution of a large scale traveling salesman problem. Tech. Rep. P-510. RAND Corp., Santa Monica, CA, 1954.

[13] Deineko V. G., Klinz B., Tiskin A., Woeginger G. J. Four-point conditions for the TSP: the complete complexity classification // Discrete Optim. 2014. Vol. 14. P. 147–159.

[14] Geist D., Rodin E. Y. Adjacency of the 0–1 knapsack problem // Comput. Oper. Res. 1992. Vol. 19, No. 8. P. 797–800.

[15] Gilmore P. C., Lawler E. L., Shmoys D. B. Well-solved special cases // The traveling salesman problem: a guided tour of combinatorial optimization. Chichester: Wiley, 1985. P. 87–143.

[16] Girlich E., Höding M., Horbach A., Kovalev M. On the facets and diameter of the $k$-cycle polytope // Optimization. 2006. Vol. 55, No. 4. P. 311–339.

[17] Grötschel M., Padberg M. Polyhedral theory // The traveling salesman problem: a guided tour of combinatorial optimization. Chichester: Wiley, 1985. P. 251–305.

[18] Padberg M. W., Rao M. R. The travelling salesman problem and a class of polyhedra of diameter two // Math. Program. 1974. Vol. 7, No. 1. P. 32–45.

[19] Papadimitriou C. H. The adjacency relation on the traveling salesman polytope is NP-complete // Math. Program. 1978. Vol. 14, No. 1. P. 312–324.

[20] Rispoli F. J., Cosares S. A bound of 4 for the diameter of the symmetric traveling salesman polytope // SIAM J. Discrete Math. 1998. Vol. 11, No. 3. P. 373–380.

[21] Sierksma G. The skeleton of the symmetric traveling salesman polytope // Discrete Appl. Math. 1993. Vol. 43, No. 1. P. 63–74.

[22] Sierksma G., Teunter R. H., Tijssen G. A. Faces of diameter two on the Hamiltonian cycle polytype // Oper. Res. Lett. 1995. Vol. 18, No. 2. P. 59–64.

[23] Sierksma G., Tijssen G. A. Faces with large diameter on the symmetric traveling salesman polytope // Oper. Res. Lett. 1992. Vol. 12, No. 2. P. 73–77.