NP-полнота задачи об эйлеровом маршруте в кратном графе
https://doi.org/10.18255/1818-1015-2024-1-102-114
Аннотация
В статье рассматриваются неориентированные кратные графы произвольной натуральной кратности $k>1$. Кратный граф содержит ребра трех типов: обычные, кратные и мультиребра. Ребра последних двух типов представляют собой объединение $k$ связанных ребер, которые соединяют 2 или $(k+1)$ вершину соответственно. Связанные ребра могут использоваться только согласованно. Если вершина инцидентна кратному ребру, то она может быть инцидентна другим кратным ребрам, а также она может быть общим концом $k$ связанных ребер мультиребра. Если вершина является общим концом мультиребра, то она не может быть общим концом никакого другого мультиребра. Рассматривается задача об эйлеровом маршруте (цикле или цепи) в кратном графе, которая обобщает классическую задачу для обычного графа. Доказывается, что задача о кратном эйлеровом маршруте в варианте распознавания является NP-полной. Для этого предварительно обосновывается NP-полнота вспомогательной задачи о покрывающих цепях с заданными концами в обычном графе.
Ключевые слова
кратный граф,
кратный путь,
делимый граф,
покрывающие цепи,
пути, не пересекающиеся по ребрам,
эйлерова цепь,
эйлеров цикл,
NP-полнота
MSC2020: 05C45, 05C65
Об авторе
Александр Валерьевич Смирнов
Ярославский государственный университет им. П.Г. Демидова
Россия
Россия
Список литературы
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. V. S. Rublev and A. V. Smirnov, “Flows in Multiple Networks,” Yaroslavsky Pedagogichesky Vestnik, vol. 3, no. 2, pp. 60–68, 2011.
3. 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.
4. L. R. Ford and D. R. Fulkerson, Flows in Networks. Princeton University Press, 1962.
5. 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.
6. 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.
7. 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.
8. 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.
9. C. Berge, Graphs and Hypergraphs. North-Holland Publishing Company, 1973.
10. 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.
11. 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.
12. 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.
13. 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.
14. 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.
15. M. Middendorf and F. Pfeiffer, “On the complexity of the disjoint paths problem,” Combinatorica, vol. 13, pp. 97–107, 1993, doi: 10.1007/BF01202792.
Рецензия
Для цитирования:
Смирнов А.В. NP-полнота задачи об эйлеровом маршруте в кратном графе. Моделирование и анализ информационных систем. 2024;31(1):102-114. https://doi.org/10.18255/1818-1015-2024-1-102-114
For citation:
Smirnov A.V. NP-completeness of the Eulerian walk problem for a multiple graph. Modeling and Analysis of Information Systems. 2024;31(1):102-114. (In Russ.) https://doi.org/10.18255/1818-1015-2024-1-102-114
Просмотров:
218
Послать статью по эл. почте 