1
правка
Изменения
м
Похоже, был копипаст из статьи про мосты. Слово "мосты" заменено на "точки сочленения".
Запустим [[Обход в глубину, цвета вершин|обход в глубину]] из произвольной вершины графа; обозначим её через <tex>root</tex>. Заметим следующий факт:
* Пусть мы находимся в обходе в глубину, просматривая сейчас все рёбра из вершины <tex>v</tex>. Тогда, если текущее ребро (<tex>v</tex>,<tex>to</tex>) таково, что из вершины <tex>to</tex> и из любого её потомка в дереве обхода в глубину нет обратного ребра в вершину <tex>v</tex> или какого-либо её предка, то это ребро эта вершина является мостомточкой сочленения. В противном случае оно мостом она ей не является. (В самом деле, мы этим условием проверяем, нет ли другого пути из <tex>v</tex> в <tex>to</tex>, кроме как спуск по ребру (<tex>v</tex>,<tex>to</tex>) дерева обхода в глубину.)
Теперь осталось научиться проверять этот факт для каждой вершины эффективно. Для этого воспользуемся "временами входа в вершину", вычисляемыми алгоритмом поиска в глубину.
