maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2021-1-22-37mais-1470Research ArticleAlgorithmsNP-полнота задачи о минимальном остовном дереве в кратном графе кратности k ≥ 3NP-completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity k ≥ 3https://orcid.org/0000-0002-0980-2507СмирновАлександр ВалерьевичSmirnovAlexander Valeryevich

Кандидат физико-математических наук, доцент, кафедра теоретической информатики

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

PhD, Associate Professor, Department of Theoretical Computer Science

14 Sovetskaya, Yaroslavl 150003

alexander_sm@mail.ruЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation2021230320212812237Copyright © Смирнов А.В., 20212021Смирнов А.В.Smirnov A.V.Данная работа распространяется под лицензией 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/1470

В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности k > 1. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение k связанных ребер, которые соединяют 2 или (k + 1) вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом k связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра. Кратное дерево определяется как связный кратный граф без циклов. В отличие от обычных деревьев количество ребер в кратных деревьях не фиксировано. Для кратного графа можно поставить задачу поиска его остовного дерева. Среди всех остовных деревьев в кратном графе выделяется особый класс – полные остовные деревья. Кратный путь между любой парой вершин в таком дереве существует тогда и только тогда, когда кратный путь между ними существует в исходном графе. Если кратный граф является взвешенным, то для него можно поставить задачу о минимальном остовном дереве, а также о минимальном полном остовном дереве. Кроме того, можно сформулировать задачи распознавания остовного и полного остовного дерева ограниченного веса. Основным результатом данной статьи является доказательство того, что указанные задачи распознавания являются NP-полными как в случае произвольных, так и в случае делимых кратных графов, если кратность k ≥ 3. Соответствующие оптимизационные задачи являются NP-трудными.

In this paper, we study undirected multiple graphs of any natural multiplicity k > 1. There are edges of three types: ordinary edges, multiple edges and multi-edges. Each edge of the last two types is a union of k linked edges, which connect 2 or (k + 1) vertices correspondingly. The linked edges should be used simultaneously. If a vertex is incident to a multiple edge, it can be also incident to other multiple edges and it can be the common end of k linked edges of some multi-edge. If a vertex is the common end of some multi-edge, it cannot be the common end of another multi-edge. A multiple tree is a connected multiple graph with no cycles. Unlike ordinary trees, the number of edges in a multiple tree is not fixed. The problem of finding the spanning tree can be set for a multiple graph. Complete spanning trees form a special class of spanning trees of a multiple graph. Their peculiarity is that a multiple path joining any two selected vertices exists in the tree if and only if such a path exists in the initial graph. If the multiple graph is weighted, the minimum spanning tree problem and the minimum complete spanning tree problem can be set. Also we can formulate the problems of recognition of the spanning tree and complete spanning tree of the limited weight. The main result of this article is the proof of NPcompleteness of such recognition problems for arbitrary multiple graphs as well as for divisible multiple graphs in the case when multiplicity k ≥ 3. The corresponding optimization problems are NP-hard.

кратный графкратное дереводелимый графостовное деревополное остовное деревоминимальное остовное деревоNP-полнотаmultiple graphmultiple treedivisible graphspanning treecomplete spanning treeminimum spanning treeNP-completenessРабота выполнена в рамках инициативной НИР ЯрГУ им. П. Г. Демидова № VIP-016This work was supported by P. G. Demidov Yaroslavl State University Project № VIP-016ReferencesA. V. Smirnov, “The Shortest Path Problem for a Multiple Graph”, Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 625–633, 2018. doi: 10.3103/S0146411618070234.A. V. Smirnov, “The Shortest Path Problem for a Multiple Graph”, Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 625–633, 2018. doi: 10.3103/S0146411618070234.A. V. Smirnov, “The Spanning Tree of a Divisible Multiple Graph”, Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 871–879, 2018. doi: 10.3103/S0146411618070325.A. V. Smirnov, “The Spanning Tree of a Divisible Multiple Graph”, Automatic Control and Computer Sciences, vol. 52, no. 7, pp. 871–879, 2018. doi: 10.3103/S0146411618070325.J. B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proceedings of the American Mathematical Society, vol. 7, no. 1, pp. 48–50, 1956. doi: 10.1090/S0002-9939-1956-0078686-7.J. B. Kruskal, “On the Shortest Spanning Subtree of a Graph and the Traveling Salesman Problem”, Proceedings of the American Mathematical Society, vol. 7, no. 1, pp. 48–50, 1956. doi: 10.1090/S0002-9939-1956-0078686-7.T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd. ‘e MIT Press, McGraw-Hill Book Company, 2009.T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd. ‘e MIT Press, McGraw-Hill Book Company, 2009.C. Berge, Graphs and Hypergraphs. North-Holland Publishing Company, 1973.C. Berge, Graphs and Hypergraphs. North-Holland Publishing Company, 1973.A. Basu and R. W. Blanning, “Metagraphs in workƒow support systems”, Decision Support Systems, vol. 25, no. 3, pp. 199–208, 1999. doi: 10.1016/S0167-9236(99)00006-8.A. Basu and R. W. Blanning, “Metagraphs in workƒow support systems”, Decision Support Systems, vol. 25, no. 3, pp. 199–208, 1999. doi: 10.1016/S0167-9236(99)00006-8.A. Basu and R. W. Blanning, Metagraphs and Their Applications, ser. Integrated Series in Information Systems. Springer US, 2007, vol. 15.A. Basu and R. W. Blanning, Metagraphs and Their Applications, ser. Integrated Series in Information Systems. Springer US, 2007, vol. 15.V. S. Rublev and A. V. Smirnov, “Flows in Multiple Networks”, Yaroslavsky Pedagogichesky Vestnik, vol. 3, no. 2, pp. 60–68, 2011.V. S. Rublev and A. V. Smirnov, “Flows in Multiple Networks”, Yaroslavsky Pedagogichesky Vestnik, vol. 3, no. 2, pp. 60–68, 2011.A. V. Smirnov, “The Problem of Finding the Maximum Multiple Flow in the Divisible Network and its Special Cases”, Automatic Control and Computer Sciences, vol. 50, no. 7, pp. 527–535, 2016. doi: 10.3103/S0146411616070191.A. V. Smirnov, “The Problem of Finding the Maximum Multiple Flow in the Divisible Network and its Special Cases”, Automatic Control and Computer Sciences, vol. 50, no. 7, pp. 527–535, 2016. doi: 10.3103/S0146411616070191.L. R. Ford and D. R. Fulkerson, Flows in Networks. Princeton University Press, 1962.L. R. Ford and D. R. Fulkerson, Flows in Networks. Princeton University Press, 1962.V. S. Roublev and A. V. Smirnov, “The Problem of Integer-Valued Balancing of a Three-Dimensional Matrix and Algorithms of Its Solution”, Modeling and Analysis of Information Systems, vol. 17, no. 2, pp. 72–98, 2010.V. S. Roublev and A. V. Smirnov, “The Problem of Integer-Valued Balancing of a Three-Dimensional Matrix and Algorithms of Its Solution”, Modeling and Analysis of Information Systems, vol. 17, no. 2, pp. 72–98, 2010.A. V. Smirnov, “Network Model for the Problem of Integer Balancing of a Four-Dimensional Matrix”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 558–566, 2017. doi: 10.3103/S0146411617070185.A. V. Smirnov, “Network Model for the Problem of Integer Balancing of a Four-Dimensional Matrix”, Automatic Control and Computer Sciences, vol. 51, no. 7, pp. 558–566, 2017. doi: 10.3103/S0146411617070185.M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness. W. H. Freeman and Company, 1979.R. Karp, “Reducibility among combinatorial problems”, in Complexity of Computer Computations, R. E. Miller and J. W. ‘atcher, Eds., Plenum, 1972, pp. 85–103. doi: 10.1007/978-1-4684-2001-2_9.R. Karp, “Reducibility among combinatorial problems”, in Complexity of Computer Computations, R. E. Miller and J. W. ‘atcher, Eds., Plenum, 1972, pp. 85–103. doi: 10.1007/978-1-4684-2001-2_9.

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