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

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

ОпределенияПравить

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

 

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

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

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

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

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

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

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

$Low(v)=min\left\{\underset{x\in <!--\; \in \; -->Ch(v)}{min}Low(x),\underset{y\in <!--\; \in \; -->Adj(v)/Ch(v)}{min}n(y)\right\}.$$Low(v)=\min \left\{\min _{x\in Ch(v)}Low(x),\min _{y\in Adj(v)/Ch(v)}n(y)\right\}.$ 

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

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

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

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

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

См. такжеПравить

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

ЛитератураПравить

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