Мост (теория графов)

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

Граф с 6 мостами (выделены красным)

Неориентированный связный граф, не имеющий разрезающих рёбер

Деревья и леса

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

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

Связь с вершинной связностью

Мосты тесно связаны с концепцией шарниров — вершин, которые входят в любой путь, соединяющий некоторые две вершины. Две конечные вершины моста являются шарнирами, если они не имеют степень 1, хотя рёбра, не являющиеся мостами, тоже могут с обоих концов иметь шарниры. Аналогично графам без мостов, которые рёберно 2-связны, графы без шарниров вершинно 2-связны.

В кубических графах любой шарнир является конечной вершиной хотя бы одного моста.

Графы без мостов

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

Важной открытой проблемой, связанной с мостами, является гипотеза о двойном покрытии циклами, высказанная Сеймуром и Секерешем (в 1978 году и 1979 году, независимо), которая утверждает, что любой граф без мостов можно покрыть простыми циклами, содержащими каждое ребро дважды.

Алгоритм поиска мостов Тарьяна

Первый алгоритм для нахождения мостов в графе, имеющий линейное время работы, описан Робертом Тарьяном в 1974 году. Алгоритм работает следующим образом:

• Находим остовный лес графа $G$.
• Создаём лес с корнями $F$ из остовного дерева.
• Обходим лес $F$ в прямом порядке и нумеруем вершины. Родительские вершины теперь имеют меньшие номера по сравнению с потомками.

Будем обозначать ребро (v,w), содержащееся в дереве, как $v\to w$, а не содержащееся — как $v--w$.

• Для каждой вершины $v$ при прямом обходе выполняем:
  • Вычисляем число потомков $ND(v)$ для вершины, добавляя единицу при переходе к следующей вершине (включая вершину $v$).

$ND(v)=1+\sum _{v\to w}ND(w)$.

• • Вычисляем $L(v)$, минимальный номер, до которого можно дойти из вершины $v$, идя по рёбрам поддерева, начинающегося в $v$ (за исключением последнего ребра). Это минимальный номер в множестве, состоящем из значений $L(w)$ потомков вершины $v$ и номеров вершин, до которых можно дойти из $v$ по рёбрам, не принадлежащим $F$.

$L(v)=\min(\{v\}\cup \{L(w)\mid v\to w\}\cup \{w\mid v--w\})$

• • Аналогичным образом вычислим $H(v)$, наибольший номер, до которого можно добраться, идя по рёбрам поддерева, начинающегося $v$. Это максимальный номер в множестве значений, состоящем из значений $H(w)$ потомков вершины $v$ и номеров вершин, до которых можно дойти из $v$ по рёбрам, не принадлежащим $F$.

$H(v)=\max(\{v\}\cup \{H(w)\mid v\to w\}\cup \{w\mid v--w\})$

• • Для каждой вершины $w$ с родителем $v$ проверяем, если $L(w)=w$ и $H(w)<w+ND(w)$, то ребро из $v$ в $w$ является мостом.

Если $v\to w$ — мост, то ясно, что из поддерева с корнем в $w$ не должно быть возможности выйти на вершину, не принадлежащую этому поддереву. Для проверки этого достаточно проверить L(w),H(w) — условие $L(w)=w$ означает, что мы не выйдем на вершину, лежащую ближе к корню, а условие $H(w)<w+ND(w)$ — что мы не выйдем на другое поддерево.

Поиск мостов с помощью разложения на цепочки

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

Разложение на цепочки — это специальный случай разложения на уши, основанный на поиске в глубину по дереву T графа G и оно может быть выполнено очень просто:

пусть все вершины помечены как непосещённые. Для всех вершин v в восходящем порядке номеров обхода 1...n, проходим каждое обратное ребро (то есть ребро, не принадлежащее дереву обхода), инцидентное вершине v, и проследуем по рёбрам дерева к корню пока не встретим посещённую вершину. Во время этого прохода помечаем все пройденные вершины как посещённые. Этот проход закончится образованием либо пути, либо цикла, начинающегося в v, мы назовём это путь или цикл цепочкой. Будем обозначать i-ю цепочку, полученную такой процедурой, как C_i. C=C₁,C₂,... является тогда разбиением графа G на цепочки.

Следующие свойства дают возможность получить некоторую информацию о графе G из C эффективно, включая все мосты:

Пусть C — разложение на цепочки простого связного графа G=(V,E).

1. G является рёберно 2-связным в том и только в том случае, когда цепочки C содержат все рёбра из E.
2. Ребро e в G является мостом в том и только в том случае, когда e не содержится ни в одной цепочке из C.
3. Если G является рёберно 2-связным, C является разложением на уши.
4. G является вершинно 2-связным в том и только в том случае, когда G имеет минимальную степень 2 и C₁ является единственным циклом в C.
5. Вершина v в рёберно 2-связном графе G является шарниром в том и только в том случае, когда v является первой вершиной в цикле из C - C₁.
6. Если G является вершинно 2-связным, C является открытым разложением на уши.