Cтраница 3
Для доказательства того, что алгоритм 2.3 корректно строит стягивающее дерево произвольного связного графа, достаточно отметить следующие три факта. Таким образом алгоритм строит связный граф. Отсюда следует, что построенный граф F, Ту не содержит циклов. Действительно, последняя ветвь, замыкающая цикл, должна была бы соединить две уже рассмотренные вершины. И наконец, в-третьих, из свойства поиска в глубину следует, что процедура WGD просматривает все вершины связного графа. Следовательно, граф F, Г, построенный нашим алгоритмом, есть стягивающее дерево графа G. Вычислительная сложность алгоритма есть, очевидно, O ( n m), а:, е, того же порядка, что и поиск в глубину. [31]