maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2015-4-453-463mais-265Research ArticleОригинальные статьиArticlesПолиэдральные графы задач об остовных деревьях при дополнительных ограничениях1-Skeletons of the Spanning Tree Problems with Additional ConstraintsБондаренкоВ. А.BondarenkoV. A.

д-р физ.-мат. наук, профессор

ул. Советская, 14, г. Ярославль, 150000, Россия

doctor of science, professor

Sovetskaya str., 14, Yaroslavl, 150000, Russia

bond@bond.edu.yar.ruНиколаевА. В.NikolaevA. V.

канд. физ.-мат. наук

ул. Советская, 14, г. Ярославль, 150000, Россия

PhD

Sovetskaya str., 14, Yaroslavl, 150000, Russia

werdan.nik@gmail.comШовгеновД. А.ShovgenovD. A.

аспирант

ул. Советская, 14, г. Ярославль, 150000, Россия

graduate student

Sovetskaya str., 14, Yaroslavl, 150000, Russia

djsh92@mail.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation201520082015224453463Copyright © Бондаренко В.А., Николаев А.В., Шовгенов Д.А., 20152015Бондаренко В.А., Николаев А.В., Шовгенов Д.А.Bondarenko V.A., Nikolaev A.V., Shovgenov D.A.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/265

Исследуются полиэдральные графы двух задач о минимальном остовном дереве при дополнительных ограничениях. В первой задаче речь идет об отыскании дерева с минимальной суммой весов ребер среди всех остовных деревьев, количество висячих вершин которых не превосходит заданную величину. Во второй задаче дополнительное ограничение заключается в предположении о том, что степени всех вершин искомого дерева не превосходят заданную величину. Обе рассматриваемые задачи в варианте распознавания являются NP-полными. В работе изучаются многогранники указанных задач и их графы. Устанавливается, что в обоих случаях распознавание смежности вершин этих графов представляет собой NP-полную задачу. Несмотря на это, удается получить сверхполиномиальные нижние оценки плотности (кликового числа) этих графов, которые характеризуют временную трудоемкость в широком классе алгоритмов, использующих линейные сравнения. Приведенные результаты свидетельствуют о принципиальном отличии комбинаторно–геометрических свойств рассматриваемых задач от классической задачи о минимальном остовном дереве.

In this paper, we study polyhedral properties of two spanning tree problems with additional constraints. In the first problem, it is required to find a tree with a minimum sum of edge weights among all spanning trees with the number of leaves less than or equal to a given value. In the second problem, an additional constraint is the assumption that the degree of all nodes of the spanning tree does not exceed a given value. The recognition versions of both problems are NP-complete. We consider polytopes of these problems and their 1-skeletons. We prove that in both cases it is a NP-complete problem to determine whether the vertices of 1-skeleton are adjacent. Although it is possible to obtain a superpolynomial lower bounds on the clique numbers of these graphs. These values characterize the time complexity in a broad class of algorithms based on linear comparisons. The results indicate a fundamental difference between combinatorial and geometric properties of the considered problems from the classical minimum spanning tree problem.

остовное деревополиэдральный графплотность графаNP-полная задачагамильтонова цепьspanning tree1-skeletonclique numberNP-complete problemhamiltonian chainReferencesБондаренко В. А., “Оценки сложности задач комбинаторной оптимизации в одном классе алгоритмов”, Доклады Академии наук, 328:1 (1993), 22–24; [Bondarenko V. A., “Complexity bounds for combinatorial optimization problems in one class of algorithms”, Russian Academy of Sciences Doklady Mathematics, 328:1 (1993), 22–24, (in Russian).]Бондаренко В. А., “Оценки сложности задач комбинаторной оптимизации в одном классе алгоритмов”, Доклады Академии наук, 328:1 (1993), 22–24; [Bondarenko V. A., “Complexity bounds for combinatorial optimization problems in one class of algorithms”, Russian Academy of Sciences Doklady Mathematics, 328:1 (1993), 22–24, (in Russian).]Бондаренко В. А., Максименко А. Н., Геометрические конструкции и сложность в комбинаторной оптимизации, ЛКИ, М., 2008, 184 с.; [Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost' v kombinatornoy optimizatsii, LKI, Moscow, 2008, (in Russian).]Бондаренко В. А., Максименко А. Н., Геометрические конструкции и сложность в комбинаторной оптимизации, ЛКИ, М., 2008, 184 с.; [Bondarenko V. A., Maksimenko A. N., Geometricheskie konstruktsii i slozhnost' v kombinatornoy optimizatsii, LKI, Moscow, 2008, (in Russian).]Бондаренко В. А., Николаев А. В., “Комбинаторно-геометрические свойства задачи о разрезе”, Доклады Академии наук, 452:2 (2013), 127–129; [Bondarenko V. A., Nikolaev A. V., “Combinatorial and Geometric Properties of the Max-Cut and Min-Cut Problems”, Doklady Mathematics, 88:2 (2013), 516–517]Бондаренко В. А., Николаев А. В., “Комбинаторно-геометрические свойства задачи о разрезе”, Доклады Академии наук, 452:2 (2013), 127–129; [Bondarenko V. A., Nikolaev A. V., “Combinatorial and Geometric Properties of the Max-Cut and Min-Cut Problems”, Doklady Mathematics, 88:2 (2013), 516–517]Пападимитриу Х., Стайглиц К., Комбинаторная оптимизация: алгоритмы и сложность, Мир, М., 1985, 512 с.; [Papadimitriou C. H., Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1982.]Пападимитриу Х., Стайглиц К., Комбинаторная оптимизация: алгоритмы и сложность, Мир, М., 1985, 512 с.; [Papadimitriou C. H., Steiglitz K., Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, Inc., Upper Saddle River, NJ, USA, 1982.]Гэри M., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, М., 1982, 416 с.; [Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1979.]Гэри M., Джонсон Д., Вычислительные машины и труднорешаемые задачи, Мир, М., 1982, 416 с.; [Garey M. R., Johnson D. S., Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, USA, 1979.]Rahman M. S., Kaykobad M., “Complexities of some interesting problems on spanning trees”, Information Processing Letters, 94:2 (2005), 93–97.Rahman M. S., Kaykobad M., “Complexities of some interesting problems on spanning trees”, Information Processing Letters, 94:2 (2005), 93–97.Fernandes L. M., Gouveia L., “Minimal spanning trees with a constraint on the number of leaves”, European Journal of Operational Research, 104:1 (1998), 250–261.Fernandes L. M., Gouveia L., “Minimal spanning trees with a constraint on the number of leaves”, European Journal of Operational Research, 104:1 (1998), 250–261.Goemans M. X., “Minimum Bounded-Degree Spanning Trees”, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, 273–282.Goemans M. X., “Minimum Bounded-Degree Spanning Trees”, Proceedings of the 47th Annual IEEE Symposium on Foundations of Computer Science, 2006, 273–282.Salamon G., Wiener G., “On finding spanning trees with few leaves”, Information Processing Letters, 105:5 (2008), 164–169.Salamon G., Wiener G., “On finding spanning trees with few leaves”, Information Processing Letters, 105:5 (2008), 164–169.Singh M., Lau L. C., “Approximating minimum bounded degree spanning trees to within one of optimal”, Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing., 2007, 661–670.Singh M., Lau L. C., “Approximating minimum bounded degree spanning trees to within one of optimal”, Proceedings of the Thirty-ninth Annual ACM Symposium on Theory of Computing., 2007, 661–670.Бренстед А., Введение в теорию выпуклых многогранников, Мир, М., 1988, 240 с.; [Brondsted A., An Introduction to Convex Polytopes, Springer-Verlag, 1983.]Бренстед А., Введение в теорию выпуклых многогранников, Мир, М., 1988, 240 с.; [Brondsted A., An Introduction to Convex Polytopes, Springer-Verlag, 1983.]Martin R. K., “Using separation algorithms to generate mixed integer model reformulations”, Operations Research Letters, 10:3 (1991), 119–128.Martin R. K., “Using separation algorithms to generate mixed integer model reformulations”, Operations Research Letters, 10:3 (1991), 119–128.Белов Ю.А., “О плотности графа матроида”, Модели исследования операций в вычислительных системах, Яросл. гос. ун-т., Ярославль, 1985, 95–100; [Belov Y. A., “O plotnosti grafa matroida”, Modeli issledovanija operacij v vychislitelnyh sistemah, Yaroslavl state university, Yaroslavl, 1985, 95–100, (in Russian).]Белов Ю.А., “О плотности графа матроида”, Модели исследования операций в вычислительных системах, Яросл. гос. ун-т., Ярославль, 1985, 95–100; [Belov Y. A., “O plotnosti grafa matroida”, Modeli issledovanija operacij v vychislitelnyh sistemah, Yaroslavl state university, Yaroslavl, 1985, 95–100, (in Russian).]Fujie T., “The maximum-leaf spanning tree problem: Formulations and facets”, Networks, 43:4 (2004), 212–223.Fujie T., “The maximum-leaf spanning tree problem: Formulations and facets”, Networks, 43:4 (2004), 212–223.Papadimitriou C. H., “The Adjacency Relation on the Traveling Salesman Polytope is NP-Complete”, Mathematical Programming, 14:1 (1978), 312–324.Papadimitriou C. H., “The Adjacency Relation on the Traveling Salesman Polytope is NP-Complete”, Mathematical Programming, 14:1 (1978), 312–324.

The authors declare that there are no conflicts of interest present.