Задача о кратчайшем пути в кратном графе

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

1. Cormen T. H., Leiserson C. E., Rivest R. L., Stein C., Introduction to Algorithms, 3rd ed., The MIT Press, McGraw-Hill Book Company, 2009.

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

3. Basu A., Blanning R.W., “Metagraphs in workflow support systems”, Decision Support Systems, 25:3 (1999), 199–208.

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

5. Рублев В. С., Смирнов А. В., “Потоки в кратных сетях”, Ярославский педагогический вестник, 3:2 (2011), 60–68;

6. Smirnov A. V., “The Problem of Finding the Maximum Multiple Flow in the Divisible Network and its Special Cases”, Automatic Control and Computer Sciences, 50:7 (2016), 527–535.

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

8. Рублев В. С., Смирнов А. В., “Задача целочисленного сбалансирования трехмерной матрицы и алгоритмы ее решения”, Моделирование и анализ информационных систем, 17:2 (2010), 72–98

9. Smirnov A. V., “Some Solvability Classes for the Problem of Integer Balancing of a Three-Dimensional Matrix with Constraints of the Second Type”, Automatic Control and Computer Sciences, 48:7 (2014), 543–553.

10. Смирнов А. В., “Сетевая модель для задачи целочисленного сбалансирования четырехмерной матрицы”, Моделирование и анализ информационных систем, 23:4 (2016), 466–478;

11. Корбут А. А., Финкельштейн Ю.Ю., Дискретное программирование, Наука, М., 1969;

12. Раскин Л. Г., Кириченко И. О., Многоиндексные задачи линейного программирования, Радио и связь, М., 1982;

13. Spieksma F. C. R., “Multi index assignment problems: complexity, approximation, applications”, Nonlinear Assignment Problems. Algorithms and Applications, eds. P. M. Pardalos, L. S. Pitsoulis, Kluwer Academic Publishers, 2000, 1–11.

14. Рублев В. С., Смирнов А. В., “NP-полнота задачи целочисленного сбалансирования трехмерной матрицы”, Доклады Академии Наук, 435:3 (2010), 314–316

15. Dijkstra E.W., “A Note on Two Problems in Connexion with Graphs”, Numerische Mathematik, 1:1 (1959), 269–271.