Нахождение критических узлов транспортной сети на основе построения замкнутой области

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