Связность графа: различия между версиями

Данный алгоритм находит 3/2-аппроксимацию для 2-реберно-связного подграфа (2-ECSS). Примем некоторую вершину r за корень дерева и запустим алгоритм DFS. Все ребра графа теперь являются либо древесными, либо обратными. Обработаем дерево DFS в обратном порядке. Для каждого поддерева выполнить следующее: если удаление ребра, ведущего от его корня к родителю, разбивает граф на два компонента, добавить самое далекое обратное ребро, ведущее из этого поддерева, у которого вторая конечная точка является наиболее близкой к r. Можно показать, что количество обратных ребер, добавленных алгоритмом, не превышает половины размера Opt.