Точка сочленения

Шарниром в теории графов называется вершина графа, при удалении которой количество компонент связности возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «точка сочленения».

Определения

Вершина $v$ графа $G$ называется шарниром, если подграф $G_{1}$, полученный из графа $G$ удалением вершины $v$ и всех инцидентных ей рёбер, состоит из большего количества компонент связности, чем исходный граф $G$.

Граф, содержащий два шарнира (вершины 2 и 5) и три блока (12, 2345, 56).

С понятием шарнира также связано понятие двусвязности. Связный граф, не содержащий шарниров, называется двусвязным. Максимальный двусвязный подграф графа называется компонентой двусвязности. Компоненты двусвязности иногда называют блоками.

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

Поиск шарниров

Эффективное решение задачи поиска всех шарниров графа основано на алгоритме поиска в глубину.

Пусть дан граф $G$. Через $Adj(v)$ обозначим множество всех вершин графа, смежных с $v$. Предположим, что мы просмотрели граф в глубину, начав с некоторой произвольной вершины. Занумеруем все вершины графа в том порядке, в котором мы их обошли, и каждой вершине $v$ припишем соответствующий номер $n(v)$. Если в вершину $u$ мы впервые попали из вершины $v$, то вершину $u$ будем называть потомком $v$, а $v$ — предком $u$. Множество всех потомков вершины $v$ обозначим через $Ch(v)$. Через $Low(v)$ обозначим минимальный номер среди всех вершин, смежных с $v$ и с теми вершинами, в которые мы пришли по пути, проходящем через $v$.

Ясно, что величину $Low(v)$ можно вычислить рекурсивно, непосредственно в процессе обхода в глубину: если в настоящий момент рассматривается вершина $v$, и из неё нельзя перейти в ещё не посещённую вершину (т.е. нужно вернуться к предку $v$, или прекратить обход, если $v$ — стартовая вершина), то для всех её потомков $Low$ уже посчитано, а значит, и для неё можно можно провести соответствующие вычисления по формуле

$Low(v)=\min \left\{\min _{x\in Ch(v)}Low(x),\min _{y\in Adj(v)/Ch(v)}n(y)\right\}.$

Зная величину $Low(v)$ для всех вершин графа, можно однозначным образом определить все его шарниры согласно следующим двум правилам:

1. Стартовая вершина (т.е. та, с которой мы начали обход) является шарниром тогда и только тогда, когда у неё больше одного потомка.
2. Вершина $v$, отличная от стартовой, является шарниром тогда и только тогда, когда у неё есть потомок u такой, что $Low(u)=n(v)$.

В качестве примера рассмотрим применение описанного алгоритма к графу, изображённому на рисунке справа. Числа, которыми помечены вершины, соответствуют одному из возможных вариантов обхода в глубину. При таком порядке у каждой из вершин ровно один потомок, за исключением вершины 6, у которой потомков нет. Стартовая вершина 1 имеет с единственного потомка, следовательно, шарниром она не является. Для остальных вершин вычислим значения интересующей нас функции:

$Low(6)=5,Low(5)=2,Low(4)=2,Low(3)=2,Low(2)=1$.

У вершины 2 есть потомок 3, а у 5 потомок 6 — в обоих случаях выполнено искомое соотношение $Low(u)=n(v)$. Следовательно, 2 и 5 являются шарнирами. Других шарниров в этом графе нет.

См. также

• Компонента связности

Литература

• В. Е. Алексеев, В. А. Таланов. Графы и алгоритмы. Структуры данных. Модели вычислений. — М.: БИНОМ. Лаборатория знаний, 2006. — ISBN 5-94774-543-7.