Рёберно k-связный граф
Рёберно k-связный граф — граф, который остаётся связным после удаления не более чем [math]\displaystyle{ k-1 }[/math] рёбер.
Часто вместо рёберно k-связный граф, говорят k-связный граф.
Формальное определение
Пусть [math]\displaystyle{ G = (V, E) }[/math] — любой граф. Если [math]\displaystyle{ G^\prime = (V, E \setminus X) }[/math] связен для всех [math]\displaystyle{ X \subseteq E }[/math] при [math]\displaystyle{ |X| \lt k }[/math], то [math]\displaystyle{ G }[/math] называется 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 — число вершин в графе, этот простой алгоритм работает за [math]\displaystyle{ O(n^2) }[/math] итераций алгоритма максимального потока, который, в свою очередь, решает задачу нахождения потока за время [math]\displaystyle{ O(n^3) }[/math]. Таким образом, общая сложность алгоритма равна [math]\displaystyle{ O(n^5) }[/math].
Улучшенный алгоритм решает задачу максимального потока для любой пары (u, v), где u — произвольная фиксированная вершина, а v пробегает все оставшиеся вершины. Этот алгоритм уменьшает сложность до [math]\displaystyle{ O(n^4) }[/math]. Если существует разрез размером меньше k, он отделяет u от некоторых других вершин. Можно улучшить алгоритм, если применить алгоритм Габова[англ.], работающий за время [math]\displaystyle{ O(n^3) }[/math][1].
Связанная задача, нахождение минимального k-рёберно-связного подграфа графа G (то есть выбрать насколько можно мало рёбер из G, которые образуют k-рёберно-связный подграф) является NP-трудной для [math]\displaystyle{ k\geq 2 }[/math][2].
См. также
- Вершинно k-связный граф
- Связный граф
- Препятствущее паросочетанию множество[англ.]
- Теорема Менгера
- Теорема Роббинса
Примечания
 | Для улучшения этой статьи желательно: |