%A Terentyeva, Yulia Yuryevna %D 2021 %T Определение максимального множества независимых простых путей между вершинами графа %K %X В настоящей статье излагается алгоритм определения максимального количества независимых простых путей, а также самих путей, между заданными вершинами графа. Данная задача крайне важна в теории связи, решение ее необходимо для обеспечения устойчивости сети связи. В то же время эта задача не рассматривается отдельной задачей в теории графов. Актуальность решения ее обусловлена, во-первых, как уже отмечалось, необходимостью повышения устойчивости сети связи, и, во-вторых, тем фактом, что для реальных сильно разветвленных сетей связи использование традиционных алгоритмов для поиска независимых маршрутов, основанных на поиске кратчайших путей, становится неэффективным.  Неэффективность объясняется тем, что при наличии, например, двух независимых маршрутов в крупномасштабных сетях связи традиционные алгоритмы поиска кратчайших путей могут обнаружить только один из-за того, что между имеющимися независимыми простыми путями существуют пути, через которые пройдет найденный стандартным алгоритмом (нахождения кратчайшего пути) путь, захватив при этом части двух имеющихся независимых маршрутов. Аналогичный эффект может быть и при наличии более двух независимых простых путей, когда стандартные алгоритмы поиска кратчайшего пути могут «потерять» все простые пути сверх одного. Предмет настоящей статьи посвящен устранению данной проблемы. %U http://sitito.cs.msu.ru/index.php/SITITO/article/view/738 %J Современные информационные технологии и ИТ-образование %0 Journal Article %R 10.25559/SITITO.17.202102.308-314 %P 308-314%V 17 %N 2 %@ 2411-1473 %8 2021-06-30