The algorithms for the Eulerian cycle and Eulerian trail problems for a multiple graph

A. V. Smirnov

Modelirovanie i analiz informacionnyh sistem, Tome 30 (2023) no. 3, pp. 264-282.

Résumé

In this paper, we study undirected multiple graphs of any natural multiplicity $k>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 $k$ linked edges, which connect $2$ or $(k+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 $k$ 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. We set the problem of finding the eulerian walk (the cycle or the trail) in a multiple graph, which generalizes the classical problem for an ordinary graph. We formulate the necessary conditions for existence of an eulerian walk in a multiple graph and show that these conditions are not sufficient. Besides that, we show that the necessary conditions of existence of an eulerian cycle and eulerian trail are not mutually exclusive for an arbitrary multiple graph, that is why it is possible to construct a multiple graph where two types of eulerian walks exist simultaneously. Any multiple graph can be juxtaposed to the ordinary graph with quasi-vertices, which represents the structure of the initial graph in a simpler form. In particular, each eulerian walk in the multiple graph corresponds to the eulerian walk in the graph with quasi-vertices. The algorithm for getting such a graph is formulated. Also, the auxiliary problem of finding the covering trails with given endpoints in an ordinary graph is studied. Two algorithms are obtained for this problem. We elaborate the algorithm for finding the eulerian walk in a multiple graph, which has the exponential complexity. We suggest the polynomial algorithm for the special case of a multiple graph and show that the necessary conditions are sufficient for existence of an eulerian walk in this special case.

Détail

Keywords: multiple graph, multiple path, reachability set, covering trails, eulerian trail, eulerian cycle, graph with quasi-vertices.
Mots-clés : divisible graph

Bibliographie

[1] A. V. Smirnov, “The shortest path problem for a multiple graph”, Automatic Control and Computer Sciences, 52:7 (2018), 625-633 | DOI | MR

[2] T. H. Cormen, C. E. Leiserson, R. L. Rivest, C. Stein, Introduction to algorithms, 3rd, The MIT Press, McGraw-Hill Book Company, 2009 | MR

[3] C. Berge, Graphs and hypergraphs, North-Holland Publishing Company, 1973 | MR | Zbl

[4] A. Basu, R. W. Blanning, “Metagraphs in workflow support systems”, Decision Support Systems, 25:3 (1999), 199-208 | DOI

[5] A. Basu, R. W. Blanning, Metagraphs and their applications, Integrated Series in Information Systems, 15, Springer US, 2007 | Zbl

[6] V. S. Rublev, A. V. Smirnov, “Flows in multiple networks”, Yaroslavsky Pedagogichesky Vestnik, 3:2 (2011), 60-68 (in Russian)

[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, 50:7 (2016), 527-535 | DOI

[8] L. R. Ford, D. R. Fulkerson, Flows in networks, Princeton University Press, 1962 | MR

[9] V. S. Roublev, 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, 17:2 (2010), 72-98 (in Russian) | MR

[10] A. V. Smirnov, “Network model for the problem of integer balancing of a four-dimensional matrix”, Automatic Control and Computer Sciences, 51:7 (2017), 558-566 | DOI | MR

[11] A. V. Smirnov, “Spanning tree of a multiple graph”, Journal of Combinatorial Optimization, 43:4 (2022), 850-869 | DOI | MR | Zbl

[12] A. V. Smirnov, “The optimized algorithm of finding the shortest path in a multiple graph”, Modeling and Analysis of Information Systems, 30:1 (2023), 6-15 (in Russian) | DOI | MR

[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, 56:7 (2022), 788-799 | DOI | MR

[14] L. Euler, “Solutio problematis ad geometriam situs pertinentis”, Commentarii Academiae Petropolitanae, 8 (1741), 128-140 (in Latin)

[15] C. Hierholzer, “Über die möglichkeit, einen linienzug ohne wiederholung und ohne unterbrechung zu umfahren”, Mathematische Annalen, 6 (1873), 30-32 (in German) | DOI | MR

[16] M. Fleury, “Deux problèmes de géométrie de situation”, Journal de mathématiques élémentaires, 2 (1883), 257-261 (in French)

[17] F. Harary, Graph theory, Addison-Wesley Pub. Co., 1969 | MR | Zbl

[18] M.-C. Cai, H. Fleischner, “An eulerian trail traversing specified edges in given order”, Journal of Graph Theory, 19:2 (1995), 137-144 | DOI | MR | Zbl

[19] M.-C. Cai, “An algorithm for an eulerian trail traversing specified edges in given order”, Discrete Applied Mathematics, 55:3 (1994), 233-239 | DOI | MR | Zbl

[20] J. Abrham, A. Kotzig, “Transformations of euler tours”, Annals of Discrete Mathematics, 8 (1980), 65-69 | DOI | MR | Zbl