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

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

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

Формальное определение[править | править исходный текст]

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

Связь минимальной степенью вершин[править | править исходный текст]

Минимальная степень вершин даёт простую верхнюю границу рёберной связности. Таким образом, для того, чтобы граф G = (V,E) являлся k-рёберно-связным, необходимо, чтобы k \le \delta(G) , где \delta(G) — минимальная степень любой вершины v \in V. Очевидно, что удаление всех рёбер, инцидентных вершине v, приведёт к отделению вершины v из графа.

Вычислительная сторона[править | править исходный текст]

Существует полиномиальный по времени алгоритм определения наибольшего 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 от некоторых других вершин. Можно улучшить алгоритм, если применить алгоритм Габова[en], работающий за время O(n^3). [1]

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