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

Некоторые алгоритмы аппроксимации для вычисления k-ECSS и k-VCSS используют подграф минимальной мощности <math>D_k \;</math> в качестве отправной точки, дополняя его добавочными ребрами таким образом, чтобы удовлетворять ограничениям связности. При использовании этого подхода получаются лучшие коэффициенты, чем при использовании подхода на базе DFS.

'''Алгоритм вычисления k-VCSS с <math>1 + \frac{1}{k}</math>'''. Найти подграф <math>D_{k-1} \;</math> минимальной мощности. Добавить столько дополнительных ребер, чтобы он стал k-связным. На этом этапе мы гарантируем, что добавленные ребра являются критическими. Из теоремы Мадера известно, что в k-связном графе цикл из критических ребер содержит по меньшей мере одну вершину степени k. Поскольку все ребра, добавляемые алгоритмом на втором этапе, являются критическими, не может существовать цикла, порожденного этими ребрами, так как степень всех вершин в таком цикле должна быть не меньше k+1. Следовательно, на этом этапе добавляются не более n-1 ребер. Количество ребер, добавленных на первом этапе к минимальному подграфу D^-i, не превышает Opt — n/2. Общее количество ребер в полученном таким образом подграфе не превышает (1 + 1/k), умноженное на количество ребер в оптимальном k-VCSS.