maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2025-2-132-149mais-1937Research ArticleDiscrete Mathematics in Relation to Computer ScienceТочный алгоритм для задачи о минимальном полном остовном дереве в делимом кратном графеExact algorithm for the problem of the minimum complete spanning tree of a divisible multiple graphhttps://orcid.org/0000-0002-0980-2507СмирновАлександр ВалерьевичSmirnovAlexander V.alexander_sm@mail.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation202528062025322132149Copyright © Смирнов А.В., 20252025Смирнов А.В.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/1937

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

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. Divisible graphs form a special class of multiple graphs. The main peculiarity of them is a possibility to divide the graph into $k$ parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. The multiple tree is a multiple graph with no multiple cycles. The number of edges may be different for multiple trees with the same number of vertices. Also we can consider spanning trees of a multiple graph. A spanning tree is complete if a multiple path joining any two selected vertices exists in the tree if and only if such a path exists in the initial graph. The problem of the minimum complete spanning tree of a multiple graph is NP-hard even in the case of a divisible graph. In this article, we obtain an exact algorithm for the problem of the minimum complete spanning tree of a divisible multiple graph. Also we define a subclass of divisible graphs, for which the algorithm runs in polynomial time.

кратный графделимый графкратное деревополное остовное деревоточный алгоритмmultiple graphdivisible graphmultiple treecomplete spanning treeexact algorithmЯрГУ (проект VIP-016).Yaroslavl State University (project VIP-016).ReferencesA. 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.A. V. Smirnov, “Spanning tree of a multiple graph,” Journal of Combinatorial Optimization, vol. 43, no. 4, pp. 850–869, 2022, doi: 10.1007/s10878-021-00810-5.A. V. Smirnov, “Spanning tree of a multiple graph,” Journal of Combinatorial Optimization, vol. 43, no. 4, pp. 850–869, 2022, doi: 10.1007/s10878-021-00810-5.A. V. Smirnov, “NP-Completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity $k geqslant 3$,” Automatic Control and Computer Sciences, vol. 56, no. 7, pp. 788–799, 2022, doi: 10.3103/S0146411622070173.A. V. Smirnov, “NP-Completeness of the Minimum Spanning Tree Problem of a Multiple Graph of Multiplicity $k geqslant 3$,” Automatic Control and Computer Sciences, vol. 56, no. 7, pp. 788–799, 2022, doi: 10.3103/S0146411622070173.T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. The MIT Press, McGraw-Hill Book Company, 2009.T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd ed. The 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 workflow 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 workflow 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, vol. 15. Springer US, 2007.A. Basu and R. W. Blanning, Metagraphs and Their Applications, vol. 15. Springer US, 2007.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.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.

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