Точка сочленения: различия между версиями

м
Check Wikipedia:Error 50, low prio \ Замена HTML-кодов на тире и длинное тире; косметические изменения
м (r2.6.5) (робот изменил: en:Biconnected component)
м (Check Wikipedia:Error 50, low prio \ Замена HTML-кодов на тире и длинное тире; косметические изменения)
'''Шарниром''' в [[Теория графов|теории графов]] называется вершина [[Граф (математика)|графа]], при удалении которой количество [[Компонента связности графа|компонент связности]] возрастает. Для обозначения этого понятия также используются термины «разделяющая вершина» и «точка сочленения».
 
== Определения ==
Вершина <math>v</math> графа <math>G</math> называется '''шарниром''', если [[подграф]] <math>G_1</math>, полученный из графа <math>G</math> удалением вершины <math>v</math> и всех инцидентных ей рёбер, состоит из большего количества компонент связности, чем исходный граф <math>G</math>.
[[ImageФайл:Sample_graph.svg|frame|Граф, содержащий два шарнира (вершины 2 и 5) и три блока (12, 2345, 56).]]
 
С понятием шарнира также связано понятие двусвязности. [[Связный граф]], не содержащий шарниров, называется '''двусвязным'''. Максимальный двусвязный подграф графа называется '''компонентой двусвязности'''. Компоненты двусвязности иногда называют блоками.
Рёберным аналогом шарнира является '''мост'''. Мостом называется такое ребро графа, в результате удаления которого количество компонент связности в графе возрастает.
 
== Поиск шарниров ==
 
Эффективное решение задачи поиска всех шарниров графа основано на [[поиск в глубину|алгоритме поиска в глубину]].
 
Пусть дан граф <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> &mdash; предком <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> &mdash; стартовая вершина), то для всех её потомков <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(6)=5, Low(5)=2, Low(4)=2, Low(3)=2, Low(2)=1</math>.
 
У вершины 2 есть потомок 3, а у 5 потомок 6 &mdash; в обоих случаях выполнено искомое соотношение <math>Low(u)=n(v)</math>. Следовательно, 2 и 5 являются шарнирами. Других шарниров в этом графе нет.
 
== См. также ==
* [[Компонента связности]]
 
== Литература ==
* {{книга
|заглавие = Графы и алгоритмы. Структуры данных. Модели вычислений.