maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2024-3-338-356mais-1881Research ArticleDiscrete Mathematics in Relation to Computer ScienceНекоторые полиномиальные подклассы задачи об эйлеровом маршруте в кратном графеSome polynomial subclasses of the Eulerian walk problem for a multiple graphhttps://orcid.org/0000-0002-0980-2507СмирновАлександр ВалерьевичSmirnovAlexander V.alexander_sm@mail.ruЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State UniversityRussian Federation202413092024313338356Copyright © Смирнов А.В., 20242024Смирнов А.В.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/1881

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

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 study 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. The multiple Eulerian walk problem is NP-hard. We prove the polynomiality of two subclasses of the multiple Eulerian walk problem and elaborate the polynomial algorithms. In the first subclass, we set a constraint on the ordinary edges reachability sets, which are the subsets of vertices joined by ordinary edges only. In the second subclass, we set a constraint on the quasi-vertices degrees in the graph with quasi-vertices. The structure of this ordinary graph reflects the structure of the multiple graph, and each quasi-vertex is determined by $k$ indices of the ordinary edges reachability sets, which are incident to some multi-edge.

кратный графделимый графпокрывающие цепипутине пересекающиеся по ребрамэйлерова цепьэйлеров циклграф с квазивершинамимножество достижимости по обычным ребрамполиномиальный подклассmultiple graphdivisible graphcovering trailsedge-disjoint pathseulerian traileulerian cyclegraph with quasi-verticesordinary edges reachability setpolynomial subclassЯрГУ (проект VIP-016).Yaroslavl State University (project VIP-016).ReferencesA. 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.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, “The algorithms for the Eulerian cycle and Eulerian trail problems for a multiple graph,” Modeling and Analysis of Information Systems, vol. 30, no. 3, pp. 264–282, 2023, doi: 10.18255/1818-1015-2023-3-264-282.A. V. Smirnov, “The algorithms for the Eulerian cycle and Eulerian trail problems for a multiple graph,” Modeling and Analysis of Information Systems, vol. 30, no. 3, pp. 264–282, 2023, doi: 10.18255/1818-1015-2023-3-264-282.C. Hierholzer, “Über die M‘oglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren,” Mathematische Annalen, vol. 6, no. 1, pp. 30–32, 1873, doi: 10.1007/BF01442866.C. Hierholzer, “Über die M‘oglichkeit, einen Linienzug ohne Wiederholung und ohne Unterbrechung zu umfahren,” Mathematische Annalen, vol. 6, no. 1, pp. 30–32, 1873, doi: 10.1007/BF01442866.C. Berge, Graphs and Hypergraphs. North-Holland Publishing Company, 1973.C. Berge, Graphs and Hypergraphs. North-Holland Publishing Company, 1973.Z. Lonc and P. Naroski, “On Tours that contain all Edges of a Hypergraph,” The Electronic Journal of Combinatorics, vol. 17, p. R144, 2010, doi: 10.37236/416.Z. Lonc and P. Naroski, “On Tours that contain all Edges of a Hypergraph,” The Electronic Journal of Combinatorics, vol. 17, p. R144, 2010, doi: 10.37236/416.A. Marino and A. Silva, “Eulerian Walks in Temporal Graphs,” Algoritmica, vol. 85, no. 3, pp. 805–830, 2023, doi: 10.1007/s00453-022-01021-y.A. Marino and A. Silva, “Eulerian Walks in Temporal Graphs,” Algoritmica, vol. 85, no. 3, pp. 805–830, 2023, doi: 10.1007/s00453-022-01021-y.S. W. Bent and U. Manber, “On non-intersecting Eulerian circuits,” Discrete Applied Mathematics, vol. 18, no. 1, pp. 87–94, 1987, doi: 10.1016/0166-218X(87)90045-X.S. W. Bent and U. Manber, “On non-intersecting Eulerian circuits,” Discrete Applied Mathematics, vol. 18, no. 1, pp. 87–94, 1987, doi: 10.1016/0166-218X(87)90045-X.S. Jimbo, “The NP-completeness of Eulerian Recurrent Length for 4-regular Eulerian Graphs,” in Proceedings of the 2014 4th International Conference on Artificial Intelligence with Applications in Engineering and Technology, 2014, pp. 155–159, doi: 10.1109/ICAIET.2014.34.S. Jimbo, “The NP-completeness of Eulerian Recurrent Length for 4-regular Eulerian Graphs,” in Proceedings of the 2014 4th International Conference on Artificial Intelligence with Applications in Engineering and Technology, 2014, pp. 155–159, doi: 10.1109/ICAIET.2014.34.A. V. Smirnov, “NP-completeness of the Eulerian walk problem for a multiple graph,” Modeling and Analysis of Information Systems, vol. 31, no. 1, pp. 102–114, 2024, doi: 10.18255/1818-1015-2024-1-102-114.A. V. Smirnov, “NP-completeness of the Eulerian walk problem for a multiple graph,” Modeling and Analysis of Information Systems, vol. 31, no. 1, pp. 102–114, 2024, doi: 10.18255/1818-1015-2024-1-102-114.J. Abrham and A. Kotzig, “Transformations of Euler Tours,” Annals of Discrete Mathematics, vol. 8, pp. 65–69, 1980, doi: 10.1016/S0167-5060(08)70852-5.J. Abrham and A. Kotzig, “Transformations of Euler Tours,” Annals of Discrete Mathematics, vol. 8, pp. 65–69, 1980, doi: 10.1016/S0167-5060(08)70852-5.R. M. Karp, “On the Computational Complexity of Combinatorial Problems,” Networks, vol. 5, no. 1, pp. 45–68, 1975, doi: 10.1002/net.1975.5.1.45.R. M. Karp, “On the Computational Complexity of Combinatorial Problems,” Networks, vol. 5, no. 1, pp. 45–68, 1975, doi: 10.1002/net.1975.5.1.45.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.F. Harary, Graph theory. Addison-Wesley Pub. Co., 1969.F. Harary, Graph theory. Addison-Wesley Pub. Co., 1969.M. Middendorf and F. Pfeiffer, “On the complexity of the disjoint paths problem,” Combinatorica, vol. 13, pp. 97–107, 1993, doi: 10.1007/BF01202792.M. Middendorf and F. Pfeiffer, “On the complexity of the disjoint paths problem,” Combinatorica, vol. 13, pp. 97–107, 1993, doi: 10.1007/BF01202792.N. Robertson and P. D. Seymour, “Graph Minors. XIII. The Disjoint Paths Problem,” Journal of Combinatorial Theory, Series B, vol. 63, no. 1, pp. 65–110, 1995, doi: 10.1006/jctb.1995.1006.N. Robertson and P. D. Seymour, “Graph Minors. XIII. The Disjoint Paths Problem,” Journal of Combinatorial Theory, Series B, vol. 63, no. 1, pp. 65–110, 1995, doi: 10.1006/jctb.1995.1006.N. Alon and M. Capalbo, “Finding Disjoint Paths in Expanders Deterministically and Online,” in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007, pp. 518–524, doi: 10.1109/FOCS.2007.19.N. Alon and M. Capalbo, “Finding Disjoint Paths in Expanders Deterministically and Online,” in Proceedings of the 48th Annual IEEE Symposium on Foundations of Computer Science (FOCS'07), 2007, pp. 518–524, doi: 10.1109/FOCS.2007.19.D. Wagner and K. Weihe, “A linear-time algorithm for edge-disjoint paths in planar graphs,” Combinatorica, vol. 15, no. 1, pp. 135–150, 1995, doi: 10.1007/BF01294465.D. Wagner and K. Weihe, “A linear-time algorithm for edge-disjoint paths in planar graphs,” Combinatorica, vol. 15, no. 1, pp. 135–150, 1995, doi: 10.1007/BF01294465.

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