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

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

'''Алгоритм вычисления k-ECSS с <math>1 + \frac{2}{k+1}</math>'''. Теорема Мадера о циклах, порожденных критическими ребрами, действует только для вершинной связности, но не для реберной. В силу этого был предложен отдельный алгоритм для вычисления k-ECSS в графах, являющихся k-реберно-связными, но не являющихся k-связными. Этот алгоритм находит подграф <math>D_k \;</math> минимальной мощности и дополняет его минимальным количеством добавочных ребер, делая подграф k-реберно-связным. Количество ребер, добавленных на последнем этапе, не превышает £^у(и — 1). Поскольку количество добавленных на первом этапе ребер не превышает Opt, общее число ребер в итоге не превышает (1+k + j