О множестве независимых путей в Графе

Резюме: В статье рассматривается проблема, которая часто встречается при расчете устойчивости, одной из основных технических характеристик сети связи с канальной коммутацией. Проблема связана с поиском резервных маршрутов заданного информационного направления связи и заключается в том, что для разветвленных широкомасштабных сетей связи известные алгоритмы поиска пути, которые обычно используются для решения этой проблемы, становятся неэффективными. Предлагаются различные алгоритмы, которые позволят найти все имеющиеся независимые простые пути между заданными вершинами графа, тем самым обеспечивая получение более точной оценки устойчивости и пропускной способности. Кроме того, решение этой задачи ввиду нахождения максимального множества независимых простых путей может найти применение при решении спектра задач маршрутизации.

Ключевые слова: сеть связи, алгоритмы на графах, поиск пути, эвристические алгоритмы.

P.P. Starikov

About many independent paths in a Graph

Summary: The article deals with a problem that often occurs when calculating stability which one of the main technical characteristics of a communication network with channel switching. The problem is related to the search for backup routes of a given information direction of communication and lies in the fact that for extensive large-scale communication networks, known pathfinding algorithms that are usually used to solve this problem become ineffective. Various algorithms are proposed that will allow finding all the available independent simple paths between the given vertices of the graph, thereby providing a more accurate estimate of stability and throughput. In addition, the solution of this problem, in view of finding the maximum set of independent simple paths, can find application in solving a range of routing problems.

Keywords: communication network, graph algorithms, pathfinding, heuristic algorithms.

DOI:10.34219/2078-8320-2021-12-6-176-181