Введение

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

В теории графов, связный граф называется k-рёберно связным, если он остаётся связным при удалении любого количества рёбер, меньшего k. Рёберная связность графа — это наибольшее значение k, для которого граф является k-рёберно связным. Рёберная связность и перечисление k-рёберно связных графов были изучены Камилем Жорданом в 1869 году.

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

Пусть G – произвольный граф. Если подграф G – V \ X связен для всех X, где |X| < k, то граф G называется k-реберно связным. Реберная связность графа G – это максимальное значение k, при котором G является k-реберно связным. Минимальный набор X, удаление которого разъединяет граф G, называется минимальным разрезом в G.

Реберная версия теоремы Менгера предоставляет альтернативную и эквивалентную характеристику в терминах реберно непересекающихся путей в графе. Граф G является k-реберно связным тогда и только тогда, когда для любых двух вершин G существует k путей, соединяющих эти вершины, при этом ни у каких двух путей нет общих ребер. В одном направлении это очевидно: если существует система таких путей, то любой набор X, содержащий менее k ребер, пересекается хотя бы с одним из этих путей, и пара вершин остается соединенной даже после удаления X. В другом направлении существование системы путей для каждой пары вершин в графе, который нельзя разъединить удалением небольшого числа ребер, можно доказать, используя теорему о максимальном потоке и минимальном разрезе из теории сетевых потоков.

Связанные понятия

Минимальная степень вершины дает тривиальную верхнюю оценку для связности по ребрам. То есть, если граф k-связен по ребрам, то необходимо, чтобы k ≤ δ(G), где δ(G) – минимальная степень любой вершины v ∈ V. Удаление всех ребер, инцидентных вершине v, отсоединит v от графа. Связность по ребрам – это двойственное понятие к длине кратчайшего цикла (окружности) в графе, в том смысле, что окружность планарного графа равна связности по ребрам его двойственного графа, и наоборот. Эти понятия объединяются в теории матроидов понятием окружности матроида, которое определяется как размер наименьшего зависимого множества в матроиде. Для графического матроида окружность матроида равна окружности базового графа, а для кографического матроида – связности по ребрам. 2-связные по ребрам графы также можно охарактеризовать отсутствием мостов, существованием ушного разложения или теоремой Роббинса, согласно которой это именно те графы, которые допускают сильную ориентацию.