Русская Википедия:Точка сочленения
Точкой сочленения (Шаблон:Lang-en) в теории графов называется вершина графа, при удалении которой количество компонент связности возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «шарнир».
Определения
Вершина <math>v</math> графа <math>G</math> называется шарниром, если подграф <math>G_1</math>, полученный из графа <math>G</math> удалением вершины <math>v</math> и всех инцидентных ей рёбер, состоит из большего количества компонент связности, чем исходный граф <math>G</math>.
С понятием шарнира также связано понятие двусвязности. Двусвязный граф - связный граф, не содержащий шарниров. Компонента двусвязности - максимальный (по включению) двусвязный подграф исходного графа. Компоненты двусвязности иногда называют блоками.
Рёберным аналогом шарнира является мост. Мостом называется такое ребро графа, в результате удаления которого количество компонент связности в графе возрастает.
Поиск шарниров
Эффективное решение задачи поиска всех шарниров графа основано на алгоритме поиска в глубину.
Пусть дан граф <math>G</math>. Через <math>Adj(v)</math> обозначим множество всех вершин графа, смежных с <math>v</math>. Предположим, что мы просмотрели граф в глубину, начав с некоторой произвольной вершины. Занумеруем все вершины графа в том порядке, в котором мы в них вошли, и каждой вершине <math>v</math> припишем соответствующий номер <math>n(v)</math>. Если в вершину <math>u</math> мы впервые попали из вершины <math>v</math>, то вершину <math>u</math> будем называть потомком <math>v</math>, а <math>v</math> — предком <math>u</math>. Множество всех потомков вершины <math>v</math> обозначим через <math>Ch(v)</math>. Через <math>Low(v)</math> обозначим минимальный номер среди всех вершин, смежных с <math>v</math> и с теми вершинами, в которые мы пришли по пути, проходящем через <math>v</math>.
Ясно, что величину <math>Low(v)</math> можно вычислить рекурсивно, непосредственно в процессе обхода в глубину: если в настоящий момент рассматривается вершина <math>v</math>, и из неё нельзя перейти в ещё не посещённую вершину (т.е. нужно вернуться к предку <math>v</math>, или прекратить обход, если <math>v</math> — стартовая вершина), то для всех её потомков <math>Low</math> уже посчитано, а значит, и для неё можно провести соответствующие вычисления по формуле
<math>Low(v) = \min \left\{\min_{x \in Ch(v)}Low(x), \min_{y \in Adj(v)/Ch(v)}n(y) \right\}.</math>
Зная величину <math>Low(v)</math> для всех вершин графа, можно однозначным образом определить все его шарниры согласно следующим двум правилам:
- Стартовая вершина (т.е. та, с которой мы начали обход) является шарниром тогда и только тогда, когда у неё больше одного потомка.
- Вершина <math>v</math>, отличная от стартовой, является шарниром тогда и только тогда, когда у неё есть потомок u такой, что <math>Low(u)=n(v)</math>.
В качестве примера рассмотрим применение описанного алгоритма к графу, изображённому на рисунке справа. Числа, которыми помечены вершины, соответствуют одному из возможных вариантов обхода в глубину. При таком порядке у каждой из вершин ровно один потомок, за исключением вершины 6, у которой потомков нет. Стартовая вершина 1 имеет единственного потомка, следовательно, шарниром она не является. Для остальных вершин вычислим значения интересующей нас функции:
<math>Low(6)=5, Low(5)=2, Low(4)=2, Low(3)=2, Low(2)=1</math>.
У вершины 2 есть потомок 3, а у 5 потомок 6 — в обоих случаях выполнено искомое соотношение <math>Low(u)=n(v)</math>. Следовательно, 2 и 5 являются шарнирами. Других шарниров в этом графе нет.
См. также
Литература
