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

Abstract

Рассмотрена задача о нахождении минимального остовного дерева при условии, что вес ребер подвержен независимым изменениям. Изучена одна из количественных характеристик устойчивости оптимальных решений этой задачи, известная как радиус устойчивости и определяемая как предельный уровень изменений веса ребер, при котором выбранное наперед оптимальное решение все еще сохраняет свою оптимальность. Выведена точная формула радиуса устойчивости минимального остовного дерева, позволяющая вычислять этот радиус за время, близкое к линейному относительно числа ребер графа. Этот результат значительно улучшает формулу радиуса устойчивости оптимального решения линейной комбинаторной задачи в общей постановке, поскольку последняя формула требует полного перебора по множеству допустимых решений, мощность которого может расти экспоненциально. = We consider a minimum spanning tree problem in the situation where weights of edges are exposed to independent perturbations. We study a quantitative characteristic of stability for a given optimal solutions of the problem. The characteristic is called the stability radius and defined as the limit level of edges weights perturbations which preserve optimality of a particular solution. We present an exact formula for the stability radius that allows calculating the radius in time which is extremely close to linear with respect to number of graph edges. This improves upon a well-known formula of an optimal solution for a linear combinatorial problem which requires complete enumeration of feasible solutions set whose cardinality may grow exponentially.