Определение максимального множества независимых простых путей между вершинами графа

  • Yulia Yuryevna Terentyeva Центр информационных технологий и систем органов исполнительной власти http://orcid.org/0000-0002-2418-003X

Аннотация

В настоящей статье излагается алгоритм определения максимального количества независимых простых путей, а также самих путей, между заданными вершинами графа. Данная задача крайне важна в теории связи, решение ее необходимо для обеспечения устойчивости сети связи. В то же время эта задача не рассматривается отдельной задачей в теории графов. Актуальность решения ее обусловлена, во-первых, как уже отмечалось, необходимостью повышения устойчивости сети связи, и, во-вторых, тем фактом, что для реальных сильно разветвленных сетей связи использование традиционных алгоритмов для поиска независимых маршрутов, основанных на поиске кратчайших путей, становится неэффективным.  Неэффективность объясняется тем, что при наличии, например, двух независимых маршрутов в крупномасштабных сетях связи традиционные алгоритмы поиска кратчайших путей могут обнаружить только один из-за того, что между имеющимися независимыми простыми путями существуют пути, через которые пройдет найденный стандартным алгоритмом (нахождения кратчайшего пути) путь, захватив при этом части двух имеющихся независимых маршрутов. Аналогичный эффект может быть и при наличии более двух независимых простых путей, когда стандартные алгоритмы поиска кратчайшего пути могут «потерять» все простые пути сверх одного. Предмет настоящей статьи посвящен устранению данной проблемы.

Сведения об авторе

Yulia Yuryevna Terentyeva, Центр информационных технологий и систем органов исполнительной власти

начальник управления анализа и методологии совершенствования информационных телекоммуникационных систем, кандидат технических наук

Литература

1. Orlov Y., et al. On the Stability of D2D Connection with the Use of Kinetic Equation for SIR Empirical Distribution. In: Ed. by V. Vishnevskiy, K. Samouylov, D. Kozyrev. Distributed Computer and Communication Networks. DCCN 2019. Lecture Notes in Computer Science. 2019; 11965:111-124. Springer, Cham. (In Eng.) DOI: https://doi.org/10.1007/978-3-030-36614-8_9
2. Berge C. Theorie des Graphes. 2nd Ed. Dunod; 1958. (In French)
3. Harary F. Graph Theory. CRC Press; 1994. 288 p. (In Eng.)
4. Diestel R. Graph Theory. Graduate Texts in Mathematics, vol. 173. 5th Ed. Springer, Berlin, Heidelberg; 2017. 428 p. (In Eng.) DOI: https://doi.org/10.1007/978-3-662-53622-3
5. Belov V.V., Vorobyov E.M., Shatalov V.E. Teoriya grafov [Graph Theory]. Higher School, Moscow; 1976. 392 p. (In Russ.)
6. Emelichev V.A., Melnikov O.I., Sarvanov V.I., Tyshkevich R.I. Lekcii po teorii grafov [Lectures on Graph Theory]. URSS, Moscow; 2009. 392 p.
7. Smagin A.A., Terentyeva Yu.Yu. A mathematical model of a counter built on the basis of the Lynch-Davison code. Journal of Instrument Engineering. 2000; 43(3):28-32. Available at: https://www.elibrary.ru/item.asp?id=24234126 (accessed 15.02.2021). (In Russ., abstract in Eng.)
8. Krichevsky R.E. Szhatie i poisk informacii [Compression and search for information]. Radio and Communications, Moscow; 1989. 168 p. (In Russ.)
9. Wentzel E.S. Teoriya veroyatnostej [Probability Theory]. Nauka, Moscow; 1969. 576 p. (In Russ.)
10. Ajemov A.S., Sannikov V.G. Obshchaya teoriya svyazi [General Theory of Communication]. Telecom, Moscow; 2020. 624 p. (In Russ.)
11. Dutta B., Jackson M. The stability and efficiency of directed communication networks. Review of Economic Design. 2000; 5(3):251-272. (In Eng.) DOI: https://doi.org/10.1007/PL00013688
12. Melnikov B.F., Meshchanin V.Y., Terentyeva Y.Y. Implementation of optimality criteria in the design of communication networks. Journal of Physics: Conference Series. Engineering and Innovative Technologies. 2020; 1515:042093. (In Eng.) DOI: https://doi.org/10.1088/1742-6596/1515/4/042093
13. Bulynin A.G., Melnikov B.F., Meshchanin, V.Y., Terentyeva. Y.Y. Optimization problem, arising in the development of high-dimensional communication networks, and some heuristic methods for solving them. Informatization and Communication. 2020; (1):34-40. (In Russ., abstract in Eng.) DOI: https://doi.org/10.34219/2078-8320-2020-11-1-34-40
14. Bulynin A.G., Melnikov B.F., Meshchanin, V.Y. and Terentyeva. Y.Y. Algorithms for designing communication networks using greedy heuristics of different types. Proceedings of the International Conference on Information Technology and Nanotechnology (ITNT-2020). Samara University, Samara; 2020. p. 856-860. Available at: https://www.elibrary.ru/item.asp?id=43576630 (accessed 15.02.2021). (In Russ., abstract in Eng.)
15. Melnikov B.F., Terentyeva. Y.Y. Building communication networks: on the application of the Kruskal’s algorithm in the problems of large dimensions. International Journal of Open Information Technologies. 2021; 9(1):13-21. Available at: https://www.elibrary.ru/item.asp?id=44584129 (accessed 15.02.2021). (In Russ., abstract in Eng.)
16. Colorni A., Dorigo M., Maniezzo V. Distributed Optimization by Ant Colonies. In: F. Varela, P. Bourgine (Eds.) Proceedings of the European Conference on Artificial Life (ECAL’91). Paris, France, Elsevier Publishing; 1991. p. 134-142. (In Eng.)
17. Dorigo M., Maniezzo V., Colorni A. Ant system: optimization by a colony of cooperating agents. IEEE Transactions on Systems, Man, and Cybernetics, Part B (Cybernetics). 1996; 26(1):29-41. (In Eng.) DOI: https://doi.org/10.1109/3477.484436
18. Gambardella L.M., Dorigo M. Ant-Q: A Reinforcement Learning Approach to the Traveling Salesman Problem. Machine Learning Proceedings. Morgan Kaufmann; 1995. p. 252-260. (In Eng.) DOI: https://doi.org/10.1016/B978-1-55860-377-6.50039-6
19. Dorigo M., Gambardella L.M. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on Evolutionary Computation. 1997; 1(1):53-66. (In Eng.) DOI: https://doi.org/10.1109/4235.585892
20. Stützle T., Hoos H. MAX-MIN Ant System and local search for the traveling salesman problem. Proceedings of 1997 IEEE International Conference on Evolutionary Computation (ICEC '97). Indianapolis, IN, USA; 1997. p. 309-314. (In Eng.) DOI: https://doi.org/10.1109/ICEC.1997.592327
21. Coltorti D., Rizzoli A.E. Ant Colony Optimization for Real-World Vehicle Routing Problems. SIGEVOlution. 2007; 2(2):2-9. (In Eng.) DOI: https://doi.org/10.1145/1329465.1329466
22. Stützle T., et al. Parameter Adaptation in Ant Colony Optimization. In: Y. Hamadi, E. Monfroy, F. Saubion (Eds.) Autonomous Search. Springer, Berlin, Heidelberg; 2011. p. 191-215. (In Eng.) DOI: https://doi.org/10.1007/978-3-642-21434-9_8
23. Li Y., Li W. Adaptive Ant Colony Optimization Algorithm Based on Information Entropy: Foundation and Application. Fundamenta Informaticae. 2007; 77(3):229-242. Available at: https://content.iospress.com/articles/fundamenta-informaticae/fi77-3-03 (accessed 15.02.2021). (In Eng.)
24. Merkle D., Middendorf M., Schmeck H. Ant colony optimization for resource-constrained project scheduling. IEEE Transactions on Evolutionary Computation. 2002; 6(4):333-346. (In Eng.) DOI: https://doi.org/10.1109/TEVC.2002.802450
25. Tavares Neto R.F., Godinho Filho M. Literature review regarding Ant Colony Optimization applied to scheduling problems: Guidelines for implementation and directions for future research. Engineering Applications of Artificial Intelligence. 2013; 26(1):150-161. (In Eng.) DOI: http://dx.doi.org/10.1016/j.engappai.2012.03.011
Опубликована
2021-06-30
Как цитировать
TERENTYEVA, Yulia Yuryevna. Определение максимального множества независимых простых путей между вершинами графа. Современные информационные технологии и ИТ-образование, [S.l.], v. 17, n. 2, p. 308-314, june 2021. ISSN 2411-1473. Доступно на: <http://sitito.cs.msu.ru/index.php/SITITO/article/view/738>. Дата доступа: 28 sep. 2022 doi: https://doi.org/10.25559/SITITO.17.202102.308-314.
Раздел
Прикладные проблемы оптимизации