Рёберная связность

Рёберная связность — это характеристика графа, равная минимальному количеству рёбер, удаление которых делает граф несвязным (то есть разбивает его на несколько компонент связности) или тривиальным (состоящим из одной вершины). Рёберная связность является одной из фундаментальных мер устойчивости графа к разрыву связей и тесно связана с понятиями вершинной связности и минимальной степени вершины.

Определение и обозначения

Формально, пусть \(G = (V, E)\) — неориентированный граф. Рёберная связность \(\lambda(G)\) определяется как наименьшее число рёбер, удаление которых увеличивает количество компонент связности графа или приводит к графу с единственной вершиной. Для несвязного графа по определению \(\lambda(G) = 0\). Для связного графа, который можно разъединить удалением одного ребра (такое ребро называется мостом), \(\lambda(G) = 1\). Считается, что для графа, состоящего из одной вершины, рёберная связность равна 0.

Рёберную связность также называют коэффициентом разреза или размером минимального разреза. Множество из \(\lambda(G)\) рёбер, удаление которых разрывает граф, называется минимальным рёберным разрезом или минимальным сечением.

Связь с другими характеристиками

Рёберная связность взаимосвязана с минимальной степенью вершины \(\delta(G)\) и вершинной связностью \(\kappa(G)\) (минимальным числом вершин, удаление которых разрывает граф). Для любого связного графа \(G\) выполняется неравенство Уитни (названное в честь Хасслера Уитни): \[ \kappa(G) \le \lambda(G) \le \delta(G) \] Здесь \(\kappa(G)\) — вершинная связность, \(\lambda(G)\) — рёберная связность, \(\delta(G)\) — минимальная степень вершины в графе.

Левая часть неравенства означает, что рёберная связность всегда не меньше вершинной. Правая часть означает, что рёберная связность не может превышать минимальное количество рёбер, инцидентных любой вершине. Это следует из того, что удаление всех рёбер, инцидентных вершине минимальной степени, гарантированно изолирует эту вершину, разрывая граф.

Примеры:

• Для полного графа \(K_n\) (n ≥ 2): \(\kappa(K_n) = \lambda(K_n) = \delta(K_n) = n - 1\).
• Для цикла \(C_n\) (n ≥ 3): \(\kappa(C_n) = 2\), \(\lambda(C_n) = 2\), \(\delta(C_n) = 2\). Для цикла длины 3 (треугольник) все три характеристики равны 2.
• Для графа-звезды \(S_n\) (одна центральная вершина соединена с \(n-1\) листьями): \(\kappa(S_n) = 1\), \(\lambda(S_n) = 1\), \(\delta(S_n) = 1\). При этом для звезды с тремя и более листьями минимальная степень равна 1 (у листьев), а рёберная и вершинная связности тоже равны 1.

Классификация по рёберной связности

Графы можно классифицировать по величине их рёберной связности:

• Несвязные графы (\(\lambda = 0\)): граф состоит из двух или более изолированных компонент связности.
• Графы с мостом (\(\lambda = 1\)): связный граф, содержащий хотя бы одно ребро, удаление которого делает граф несвязным. Такие графы называют 1-рёберно-связными или сепарабельными по рёбрам.
• 2-рёберно-связные графы (\(\lambda = 2\)): граф, который остаётся связным после удаления любого одного ребра, но может быть разъединён удалением некоторой пары рёбер. Классический пример — простой цикл.
• k-рёберно-связные графы (\(\lambda \ge k\)): граф, для разъединения которого требуется удалить не менее \(k\) рёбер. Граф называется \(k\)-рёберно-связным, если \(\lambda(G) \ge k\). Полный граф \(K_n\) является \((n-1)\)-рёберно-связным.

Важно различать термины «рёберная связность» (число) и «рёберно-связный граф» (свойство). Граф с \(\lambda = 3\) является 3-рёберно-связным.

Вычисление рёберной связности

Вычисление рёберной связности графа является полиномиальной задачей. Алгоритмически она сводится к нахождению минимального разреза между парой вершин и повторению этой процедуры для всех пар (или эффективнее — с помощью алгоритма Штор-Вагнера).

Алгоритмы:

1. Алгоритм максимального потока / минимального разреза: Для каждой пары вершин \((s, t)\) найти минимальный рёберный разрез между \(s\) и \(t\). Минимум по всем таким разрезам даёт \(\lambda(G)\). Эта задача решается с помощью алгоритмов поиска максимального потока (например, алгоритм Форда — Фалкерсона или Эдмондса — Карпа). Сложность для неориентированного графа составляет \(O(|V| \cdot |E| \cdot \text{поток})\).
2. Алгоритм Штор-Вагнера (1997): находит глобальный минимальный разрез без преобразования в потоковую задачу. Его сложность составляет \(O(|V| \cdot |E| + |V|^2 \log |V|)\). Он особенно эффективен для плотных графов.

Для простых случаев, таких как деревья, рёберная связность равна 1 (если в дереве больше одной вершины).

Применение

Понятие рёберной связности находит применение в различных областях, где требуется оценка надёжности и устойчивости сетей:

• Теория сетей связи: рёберная связность коммуникационной сети (например, Интернета, телефонной сети) определяет минимальное количество линий связи, выход из строя которых приведёт к потере связи между некоторыми узлами. Высокая рёберная связность является показателем отказоустойчивости сети.
• Транспортные сети: в дорожных и транспортных системах рёберная связность показывает устойчивость маршрутов к перекрытию дорог. Проектирование сетей с высокой рёберной связностью — одна из задач транспортного планирования.
• Распределённые вычисления: в сетях распределённых систем (например, в кластерах) рёберная связность влияет на устойчивость к сбоям каналов связи.
• Биология и нейронауки: при анализе нейронных сетей и белковых взаимодействий рёберная связность используется для оценки прочности связей между функциональными модулями.
• Теория кодирования и криптография: в некоторых протоколах распределённого хранения данных и секретного разделения секрета используется понятие разреза для достижения избыточности.

Связь с двусвязностью и триангуляцией

В графе, являющемся 2-рёберно-связным (то есть не имеющем мостов), существует понятие блоков — максимальных подграфов, не содержащих точек сочленения (вершин, удаление которых разрывает граф). Однако если граф не имеет мостов, это не обязательно означает отсутствие точек сочленения. Граф, не имеющий ни мостов, ни точек сочленения, называется 3-вершинно-связным (или просто 3-связным). В такой граф можно вложить любую триангуляцию. Рёберная связность является более слабым, но важным критерием, так как модель рёберных отказов часто легче анализируется, чем модель вершинных отказов.

Примеры в графах

• Дерево: \(\lambda = 1\). Любое ребро дерева является мостом.
• Простой цикл \(C_n\) (n ≥ 3): \(\lambda = 2\). Удаление одного ребра превращает цикл в путь (связность не теряется), удаление двух определённых рёбер разбивает его на две цепи.
• Полный двудольный граф \(K_{a, b}\) (a ≤ b): \(\lambda = a\). Минимальный разрез достигается удалением всех рёбер, выходящих из меньшей доли. Например, \(K_{3, 4}\) имеет \(\lambda = 3\).
• Куб (\(Q_3\)): это 3-регулярный граф. Его рёберная связность равна 3, что соответствует нижней границе для куба.

История

Понятие рёберной связности впервые было формально введено в середине XX века в связи с развитием теории графов и сетевого анализа. Основополагающие работы в этой области принадлежат Хасслеру Уитни (1932), который сформулировал неравенство, связывающее вершинную и рёберную связности. Позднее, в 1950-е годы, с развитием теории потоков в сетях (Л. Форд, Д. Фалкерсон) задача вычисления рёберной связности была сведена к задаче поиска минимального разреза, что дало мощный вычислительный инструмент. Современные алгоритмы, такие как алгоритм Штор-Вагнера, появились в 1990-е годы и позволили эффективно решать эту задачу для графов с миллионами рёбер.

Источники:

1. Харари Ф. «Теория графов». — М.: Мир, 1973.
2. Дистель Р. «Теория графов». — Новосибирск: Издательство Института математики, 2002.
3. Свами М., Тхуласираман К. «Графы, сети и алгоритмы». — М.: Мир, 1984.
4. Stoer M., Wagner F. «A simple min-cut algorithm». — Journal of the ACM, 1997.
5. Кормен Т., Лейзерсон Ч., Ривест Р., Штайн К. «Алгоритмы: построение и анализ», 3-е изд. — М.: Вильямс, 2013.