Полиномиальный алгоритм поиска кратчайшего пути в делимом кратном графе

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

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. T. H. Cormen, C. E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms, 3rd. The MIT Press, McGraw-Hill Book Company, 2009.

3. C. Berge, Graphs and Hypergraphs. North-Holland Publishing Company, 1973.

4. 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.

5. A. Basu and R. W. Blanning, Metagraphs and Their Applications, ser.Integrated Series in Information Systems. Springer US, 2007, vol. 15.

6. V. S.Rublev and A. V. Smirnov, "Flows in Multiple Networks”, Yaroslavsky Pedagogichesky Vestnik, vol. 3, no. 2, pp. 60-68, 2011.

7. 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.

8. L. R. Ford and D. R. Fulkerson, Flows in Networks. Princeton University Press, 1962.

9. 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.

10. 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.

11. 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.

12. 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.