Точный алгоритм для задачи о минимальном полном остовном дереве в делимом кратном графе
https://doi.org/10.18255/1818-1015-2025-2-132-149
Аннотация
В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности $k>1$. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение $k$ связанных ребер, которые соединяют 2 или $(k+1)$ вершину соответственно. Связанные ребра могут использоваться только согласованно. Делимые графы представляют собой специальный класс кратных графов. Их основная особенность состоит в возможности разделить граф на $k$ частей, которые будут согласованы на связанных ребрах и не будут иметь общих ребер. Каждая часть является обычным графом. Кратное дерево представляет собой кратный граф без кратных циклов. Количество ребер может быть разным для кратных деревьев с одинаковым количеством вершин. Также можно рассмотреть остовные деревья в кратном графе. Остовное дерево является полным, если кратный путь, соединяющий любые две выбранные вершины, существует в дереве тогда и только тогда, когда такой путь существует в исходном графе. Задача о минимальном полном остовном дереве в кратном графе NP-трудна даже в случае делимого графа. В данной статье мы получим точный алгоритм для задачи о минимальном полном остовном дереве в делимом кратном графе. Также мы определим подкласс делимых графов, для которых алгоритм будет выполняться за полиномиальное время.
Об авторе
Александр Валерьевич Смирнов
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
Список литературы
1. 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.
2. 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.
3. 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.
4. 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.
5. 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.
6. C. Berge, Graphs and Hypergraphs. North-Holland Publishing Company, 1973.
7. 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.
8. A. Basu and R. W. Blanning, Metagraphs and Their Applications, vol. 15. Springer US, 2007.
9. V. S. Rublev and A. V. Smirnov, “Flows in Multiple Networks,” Yaroslavsky Pedagogichesky Vestnik, vol. 3, no. 2, pp. 60–68, 2011.
10. 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.
11. L. R. Ford and D. R. Fulkerson, Flows in Networks. Princeton University Press, 1962.
12. 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.
13. 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.
14. 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.
Рецензия
Для цитирования:
Смирнов А.В. Точный алгоритм для задачи о минимальном полном остовном дереве в делимом кратном графе. Моделирование и анализ информационных систем. 2025;32(2):132-149. https://doi.org/10.18255/1818-1015-2025-2-132-149
For citation:
Smirnov A.V. Exact algorithm for the problem of the minimum complete spanning tree of a divisible multiple graph. Modeling and Analysis of Information Systems. 2025;32(2):132-149. (In Russ.) https://doi.org/10.18255/1818-1015-2025-2-132-149
Просмотров:
26
Послать статью по эл. почте 