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

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

Определения

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

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

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

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

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

Пусть дан граф G {displaystyle G} . Через A d j ( v ) {displaystyle Adj(v)} обозначим множество всех вершин графа, смежных с v {displaystyle v} . Предположим, что мы просмотрели граф в глубину, начав с некоторой произвольной вершины. Занумеруем все вершины графа в том порядке, в котором мы в них вошли, и каждой вершине v {displaystyle v} припишем соответствующий номер n ( v ) {displaystyle n(v)} . Если в вершину u {displaystyle u} мы впервые попали из вершины v {displaystyle v} , то вершину u {displaystyle u} будем называть потомком v {displaystyle v} , а v {displaystyle v} — предком u {displaystyle u} . Множество всех потомков вершины v {displaystyle v} обозначим через C h ( v ) {displaystyle Ch(v)} . Через L o w ( v ) {displaystyle Low(v)} обозначим минимальный номер среди всех вершин, смежных с v {displaystyle v} и с теми вершинами, в которые мы пришли по пути, проходящем через v {displaystyle v} .

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

L o w ( v ) = min { min x ∈ C h ( v ) L o w ( x ) , min y ∈ A d j ( v ) / C h ( v ) n ( y ) } . {displaystyle Low(v)=min left{min _{xin Ch(v)}Low(x),min _{yin Adj(v)/Ch(v)}n(y) ight}.}

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

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

Вершина v {displaystyle v} , отличная от стартовой, является шарниром тогда и только тогда, когда у неё есть потомок u такой, что L o w ( u ) = n ( v ) {displaystyle Low(u)=n(v)} .

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

L o w ( 6 ) = 5 , L o w ( 5 ) = 2 , L o w ( 4 ) = 2 , L o w ( 3 ) = 2 , L o w ( 2 ) = 1 {displaystyle Low(6)=5,Low(5)=2,Low(4)=2,Low(3)=2,Low(2)=1} .

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