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

Материал из Википедии — свободной энциклопедии
Перейти к навигации Перейти к поиску
Пример двусвязного графа

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

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

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

[править | править код]

Пусть — любой граф. Если связен для всех при , то называется k-рёберно связен.

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

Вычисление

[править | править код]

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

Если n — число вершин в графе, этот простой алгоритм работает за итераций алгоритма максимального потока, который, в свою очередь, решает задачу нахождения потока за время . Таким образом, общая сложность алгоритма равна .

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

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

Примечания

[править | править код]
  1. Harold N. Gabow. A matroid approach to finding edge connectivity and packing arborescences. J. Comput. Syst. Sci., 50(2):259–273, 1995.
  2. M.R. Garey and D.S. Johnson. Computers and Intractability: a Guide to the Theory of NP-Completeness. Freeman, San Francisco, CA, 1979.