Алгоритмы поиска остова во взвешенном графе: различия между версиями

В данной статье представлены два простейших алгоритма, вычисляющих (2k–1)-остов заданного взвешенного графа G = (V, E). Пусть n и m – число вершин и дуг графа G, соответственно. Первый алгоритм, разработанный Альтхофером и коллегами [2], основан на [[жадный алгоритм|жадной стратегии]] и исполняется за время <math>O(mn^{1+\frac{1}{k}})</math>. Второй алгоритм [6] основан на сверхлокальном подходе, он исполняется за время O(km). Для начала рассмотрим следующее простое наблюдение. Предположим, что имеется подмножество <math>E_{s} \in E</math>, такое, что для каждой дуги <math>(x, y) \in E \setminus E_{s}</math> выполняется следующее утверждение.

P<math>_{t}</math>(x, y): вершины x и y связаны в подграфе (V, E<math>_{S}</math>) путем, состоящим из не более чем t дуг, причем вес каждой дуги на этом пути не превышает вес дуги (x, y).