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

3 байта убрано ,  7 лет назад
м (бот удалил: fa:یال برشی (strong connection between (2) ru:Шарнир (теория графов) and fa:مؤلفه دوهمبند))
# Вершина <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>.
Анонимный участник