К нахождению радиуса устойчивости минимального остовного дерева

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