Точка сочленения
Точкой сочленения (англ. articulation point) в теории графов называется вершина графа, при удалении которой количество компонент связности возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «шарнир».
Определения
[править | править код]Вершина графа называется шарниром, если подграф , полученный из графа удалением вершины и всех инцидентных ей рёбер, состоит из большего количества компонент связности, чем исходный граф .
С понятием шарнира также связано понятие двусвязности. Двусвязный граф - связный граф, не содержащий шарниров. Компонента двусвязности - максимальный (по включению) двусвязный подграф исходного графа. Компоненты двусвязности иногда называют блоками.
Рёберным аналогом шарнира является мост. Мостом называется такое ребро графа, в результате удаления которого количество компонент связности в графе возрастает.
Поиск шарниров
[править | править код]Эффективное решение задачи поиска всех шарниров графа основано на алгоритме поиска в глубину.
Пусть дан граф . Через обозначим множество всех вершин графа, смежных с . Предположим, что мы просмотрели граф в глубину, начав с некоторой произвольной вершины. Занумеруем все вершины графа в том порядке, в котором мы в них вошли, и каждой вершине припишем соответствующий номер . Если в вершину мы впервые попали из вершины , то вершину будем называть потомком , а — предком . Множество всех потомков вершины обозначим через . Через обозначим минимальный номер среди всех вершин, смежных с и с теми вершинами, в которые мы пришли по пути, проходящем через .
Ясно, что величину можно вычислить рекурсивно, непосредственно в процессе обхода в глубину: если в настоящий момент рассматривается вершина , и из неё нельзя перейти в ещё не посещённую вершину (т.е. нужно вернуться к предку , или прекратить обход, если — стартовая вершина), то для всех её потомков уже посчитано, а значит, и для неё можно провести соответствующие вычисления по формуле
Зная величину для всех вершин графа, можно однозначным образом определить все его шарниры согласно следующим двум правилам:
- Стартовая вершина (т.е. та, с которой мы начали обход) является шарниром тогда и только тогда, когда у неё больше одного потомка.
- Вершина , отличная от стартовой, является шарниром тогда и только тогда, когда у неё есть потомок u такой, что .
В качестве примера рассмотрим применение описанного алгоритма к графу, изображённому на рисунке справа. Числа, которыми помечены вершины, соответствуют одному из возможных вариантов обхода в глубину. При таком порядке у каждой из вершин ровно один потомок, за исключением вершины 6, у которой потомков нет. Стартовая вершина 1 имеет единственного потомка, следовательно, шарниром она не является. Для остальных вершин вычислим значения интересующей нас функции:
.
У вершины 2 есть потомок 3, а у 5 потомок 6 — в обоих случаях выполнено искомое соотношение . Следовательно, 2 и 5 являются шарнирами. Других шарниров в этом графе нет.
См. также
[править | править код]Литература
[править | править код]- В. Е. Алексеев, В. А. Таланов. Графы и алгоритмы. Структуры данных. Модели вычислений. — М.: БИНОМ. Лаборатория знаний, 2006. — ISBN 5-94774-543-7.