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

м
опечатка
м
Метки: визуальный редактор правка с мобильного устройства правка из мобильной версии
м (опечатка)
Пусть дан граф <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>