maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2022-4-372-387mais-1753Research ArticleAlgorithmsПолиномиальный алгоритм поиска кратчайшего пути в делимом кратном графеThe Polynomial Algorithm of Finding the Shortest Path in a Divisible Multiple Graphhttps://orcid.org/0000-0002-0980-2507СмирновАлександр ВалерьевичSmirnovAlexander Valeryevichalexander_sm@mail.ruЯрославский государственный университет им. П. Г. ДемидоваРоссияP. G. Demidov Yaroslavl State UniversityRussian Federation202218122022294372387Copyright © Смирнов А.В., 20222022Смирнов А.В.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/1753

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

In this paper, we study undirected multiple graphs of any natural multiplicity к > 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 к linked edges, which connect 2 or (к + 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 к 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. Divisible multiple graphs are characterized by a possibility to divide the graph into к parts, which are adjusted on the linked edges and which have no common edges. Each part is an ordinary graph. As for an ordinary graph, we can define the integer function of the length of an edge for a multiple graph and set the problem of the shortest path joining two vertices. Any multiple path is a union of к ordinary paths, which are adjusted on the linked edges of all multiple and multi-edges. In the article, we show that the problem of the shortest path is polynomial for a divisible multiple graph. The corresponding polynomial algorithm is formulated. Also we suggest the modification of the algorithm for the case of an arbitrary multiple graph. This modification has an exponential complexity in the parameter к.

кратный графделимый графкратный путькратчайший путьмножество достижимостиполиномиальный алгоритмmultiple graphdivisible graphmultiple pathshortest pathreachability setpolynomial algorithmReferencesA. 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.T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd. The MIT Press, McGraw-Hill Book Company, 2009.T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd. 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, 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.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.E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik, vol. 1, no. 1, pp. 269-271, 1959. doi: 10.1007/BF01386390.E. W. Dijkstra, "A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik, vol. 1, no. 1, pp. 269-271, 1959. doi: 10.1007/BF01386390.

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