WikiSort.ru - Не сортированное

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

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

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

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

Свойства

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

Вычисление

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

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

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

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

См. также

• k-вершинно-связный граф
• Связный граф
• Препятствущее паросочетанию множество^[en]
• Теорема Менгера
• Теорема Роббинса

Примечания

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка.