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

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

Определения

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

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

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

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

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

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

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

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

[math]\displaystyle{ Low(v) = \min \left\{\min_{x \in Ch(v)}Low(x), \min_{y \in Adj(v)/Ch(v)}n(y) \right\}. }[/math]

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

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

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

[math]\displaystyle{ Low(6)=5, Low(5)=2, Low(4)=2, Low(3)=2, Low(2)=1 }[/math].

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

См. также

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

Литература

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