Алгоритмы для задач об эйлеровом цикле и эйлеровой цепи в кратном графе

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

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.

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

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.

5. A. Basu and R. W. Blanning, Metagraphs and Their Applications, vol. 15. Springer US, 2007.

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.

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.

11. A. V. Smirnov, “Spanning tree of a multiple graph,” Journal of Combinatorial Optimization, vol. 43, no. 4, pp. 850–869, 2022.

12. A. V. Smirnov, “The Optimized Algorithm of Finding the Shortest Path in a Multiple Graph,” Modeling and Analysis of Information Systems, vol. 30, no. 1, pp. 6–15, 2023.

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

14. L. Euler, “Solutio problematis ad geometriam situs pertinentis,” Commentarii Academiae Petropolitanae, vol. 8, pp. 128–140, 1741.

15. C. Hierholzer, “Über die M‘oglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren,” Mathematische Annalen, vol. 6, pp. 30–32, 1873.

16. M. Fleury, “Deux probl`emes de g'eom'etrie de situation,” Journal de math'ematiques 'el'ementaires, vol. 2, pp. 257–261, 1883.

17. F. Harary, Graph theory. Addison-Wesley Pub. Co., 1969.

18. M.-C. Cai and H. Fleischner, “An Eulerian Trail Traversing Specified Edges in Given Order,” Journal of Graph Theory, vol. 19, no. 2, pp. 137–144, 1995.

19. M.-C. Cai, “An Algorithm for an Eulerian Trail Traversing Specified Edges in Given Order,” Discrete Applied Mathematics, vol. 55, no. 3, pp. 233–239, 1994.

20. J. Abrham and A. Kotzig, “Transformations of Euler Tours,” Annals of Discrete Mathematics, vol. 8, pp. 65–69, 1980.