Interested Article - Рёберно k-связный граф

Рёберно k -связный граф — граф , который остаётся связным после удаления не более чем $k-1$ рёбер.

Часто вместо рёберно k -связный граф, говорят k -связный граф.

Формальное определение

Пусть $G=(V,E)$ — любой граф. Если $G^{\prime }=(V,E\setminus X)$ связен для всех $X\subseteq E$ при $|X|<k$ , то $G$ называется k -рёберно связен.

Замечания

Если граф является рёберно k -связным, то он также и рёберно m -связен при всех m < k .
Связный граф это то же, что и рёберно 1-связный граф.

Свойства

Минимальная степень вершин рёберно k -связного графа не меньше k .
Критический граф с хроматическим числом > k является рёберно k -связным.

Вычисление

Существует полиномиальный по времени алгоритм определения наибольшего k , для которого граф G является k -рёберно-связным. В качестве простого алгоритма можно использовать следующий: для любой пары вершин (u, v) определим максимальный поток из u в v с пропускной способностью всех рёбер, равной единице в обоих направлениях. Граф является k -рёберно-связным, тогда и только тогда, когда максимальный поток из u в v не меньше k для любой пары (u, v) . Таким образом k является наименьшим u-v -потоком среди всех пар (u, v) .

Если n — число вершин в графе, этот простой алгоритм работает за $O(n^{2})$ итераций алгоритма максимального потока, который, в свою очередь, решает задачу нахождения потока за время $O(n^{3})$ . Таким образом, общая сложность алгоритма равна $O(n^{5})$ .

Улучшенный алгоритм решает задачу максимального потока для любой пары (u, v) , где u — произвольная фиксированная вершина, а v пробегает все оставшиеся вершины. Этот алгоритм уменьшает сложность до $O(n^{4})$ . Если существует разрез размером меньше k , он отделяет u от некоторых других вершин. Можно улучшить алгоритм, если применить , работающий за время $O(n^{3})$ .

Связанная задача, нахождение минимального k -рёберно-связного подграфа графа G (то есть выбрать насколько можно мало рёбер из G , которые образуют k -рёберно-связный подграф) является NP-трудной для $k\geq 2$ .

См. также

Примечания

Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci. , 50(2):259–273, 1995.
M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness . Freeman, San Francisco, CA, 1979.