Информатика · объяснение и практика

Точка сочленения: когда удаление вершины разделяет граф

Точки сочленения: удаление вершины со связями, особое правило корня DFS и отличие от мостового ребра.

Синие фигурные скобки держат между собой оранжевый квадрат.

В теме Графы и маршруты · Учебная карта

В маршруте Графы, разрезы и динамические запросы · 10 тем

Главная мысль

Точка сочленения — вершина неориентированного графа, удаление которой вместе с инцидентными рёбрами увеличивает число компонент связности. Для обычной вершины DFS и корня дерева обхода применяют разные условия. Степень вершины сама по себе ответа не даёт.

Меняем узел, а не одну связь

Представим сеть переходов между помещениями. При проверке точки сочленения полностью закрывают один узел и все связи с ним. Затем смотрят, распались ли оставшиеся вершины на большее число отдельных компонент. Это другая операция, чем удаление единственного ребра при поиске мостов.

В треугольнике A−B−C−A добавим вершину D,соединённую только с A. Если удалить A,останется связанная пара B,C и отдельная D. Компонент станет две вместо одной, поэтому A является точкой сочленения. Если удалить D,останется целый треугольник: число компонент не увеличится.

Проверяем поддерево у некорневой вершины

В поиске в глубину tin фиксирует момент входа, а low описывает самый ранний достижимый вход из поддерева через допустимые обратные связи. У некорневой вершины v достаточно найти ребёнка to,для которого low[to]≥tin[v]. Это поддерево не имеет обхода к строгим предкам v без самой v.

Знак здесь не такой, как у моста. Возврат поддерева ровно к v спасает от удаления одного ребра, но не спасает от удаления самой v. Поэтому равенство low[to]=tin[v]входит в условие точки сочленения для некорневой вершины. Если без объяснения заменить≥на>,можно пропустить реальный разрыв.

Пример

Треугольник A−B−C−A и ребро A−D: точка сочленения A,но не D.

У A есть часть сети, которая после её удаления теряет связь с остальными. Удаление листа D не разрывает оставшийся треугольник.

Почему корень обхода рассматривают отдельно

У корня DFS нет родительской части дерева, которую надо отделять от потомков. Он становится точкой сочленения, только если имеет не менее двух детей именно в дереве обхода. Число соседей в исходном графе не равно автоматически числу таких детей: часть соседей может быть достигнута через первое поддерево.

В треугольнике выбранный корень имеет два соседа, но обычный DFS может пройти обоих через одного ребёнка дерева. Удаление корня оставит ребро между двумя оставшимися вершинами, поэтому разрыва не будет. Для несвязного входа особое правило корня применяется отдельно к каждому дереву леса обхода, а не только к первой вершине всего запуска.

От чтения к действию

А теперь — вы

Корень DFS имеет трёх соседей в исходном графе, но только одного ребёнка в дереве обхода. Достаточно ли трёх соседей для признания точкой сочленения?

Частые вопросы

Вершина степени 2 обязательно является точкой сочленения?

Нет. Например, в треугольнике удаление любой вершины оставляет связанное ребро.

Корень DFS проверяется общим условием некорневой вершины?

Нет. Для корня важно наличие хотя бы двух детей дерева обхода.

Углублённый разбор

Блоки двусвязности и дерево точек сочленения

Точки сочленения указывают уязвимые вершины, но не описывают, какие части графа удерживаются вместе между ними. Блоки двусвязности разбивают рёбра на максимальные устойчивые участки. Их связи через общие точки сочленения образуют дерево, удобное для анализа отказов и маршрутов.

Перед началом: DFS и low; Точка сочленения.

Рёбра делятся на блоки, вершины могут повторяться

Работаем с конечным простым неориентированным связным графом хотя бы из двух вершин. Блоками считаем максимальные двусвязные подграфы и отдельные мосты как вырожденные блоки из одного ребра. Внутри нет точки, удаление которой разрывает оставшуюся часть блока. Разные блоки имеют не больше одной общей вершины, а каждое ребро принадлежит ровно одному блоку.

Общая вершина нескольких блоков является точкой сочленения исходного графа. Поэтому блоки не образуют разбиение множества вершин: критическая вершина законно повторяется в нескольких списках. Сильно связные компоненты ориентированного графа устроены иначе и разделяют вершины, поэтому переносить их формат результата на блоки нельзя. Изолированные вершины в несвязном графе можно дополнительно оформить одноэлементными блоками по явно выбранному соглашению.

Стек рёбер хранит ещё не завершённый блок

Во время DFS помещаем в стек каждое древесное ребро перед спуском и каждое обратное ребро к строгому предку ровно один раз. После возврата от ребёнка w вершины v условие low[w]≥tin[v] означает завершение блока. Снимаем рёбра с вершины стека до древесного ребра vw включительно: они составляют один максимальный блок. Остальные рёбра стека ещё ждут более ранней границы.

Равенство здесь существенно: поддерево может возвращаться к v, но не к её строгим предкам, поэтому его блок присоединяется к остальному через v. Для моста снятый блок состоит только из vw. У корня граница блока также обрабатывается по детям, хотя сам корень является точкой сочленения лишь при нескольких DFS-детях. Выделение блока и маркировка корня как уязвимой вершины — связанные, но разные действия.

Дерево блоков восстанавливает структуру соединения

Создадим двудольный граф: одна группа узлов — блоки, другая — точки сочленения; соединяем их по принадлежности вершины блоку. Для связного исходного графа получается дерево. Цикл таких связей означал бы обход между блоками без единственной общей вершины и противоречил бы их максимальности. Для несвязного входа получается лес. Удаление узла точки сочленения из этого дерева сразу показывает, какие группы блоков теряют связь, без повторного анализа всех внутренних рёбер.

Три блока при отсутствии мостов в треугольниках

Условие. В графе рёбра AB,BC,CA,CD,DE,EC,EF. Найдите блоки и дерево их связей. Используйте DFS A,B,C,D,E,F.

  1. По порядку обхода входы равны 1,2,3,4,5,6. Обратные рёбра C→A и E→C дают low[C]=1 и low[E]=3; у F low[F]=6.
  2. При возврате F→E условие 6≥5 снимает одно ребро EF: это мостовой блок. При возврате D→C условие low[D]=3≥tin[C]=3 снимает CD,DE,EC — треугольный блок.
  3. При возврате B→A условие low[B]=1≥tin[A]=1 снимает AB,BC,CA. Получены блоки B₁={A,B,C}, B₂={C,D,E}, B₃={E,F}.
  4. Точки сочленения C,E принадлежат по двум блокам. Дерево имеет цепь B₁–C–B₂–E–B₃. Корень A имеет одного DFS-ребёнка и точкой сочленения не является.

Ответ. Блоки ABC,CDE,EF; дерево блоков — цепь через точки C и E.

Проверка. Независимо каждый треугольник остаётся связным после удаления любой своей вершины, EF является мостом, а объединить соседние блоки мешает их единственная общая точка. Проверка удаления каждой вершины находит ровно C,E.

Где легко ошибиться. Не требуйте непересечения блоков по вершинам: общие точки сочленения являются самой полезной частью структуры. Непересекающимися должны быть списки рёбер блоков.

Проверьте понимание

Сколько блоков при указанном соглашении имеет граф задачи?

Вопросы к этой главе

Почему мост считается блоком, хотя в нём нет цикла?

Это явное расширение соглашения, позволяющее каждое ребро графа отнести ровно к одному блоку и сохранить дерево связей. Для строгой двусвязности обычно требуют хотя бы3 вершины; мост оформляется отдельным вырожденным случаем.

Почему снятие ABC у корня не делает A точкой сочленения?

Снятие завершает один блок стека. У корня нет родительской части, поэтому один ребёнок не создаёт разделение. В графе после удаления A вершины B,C всё ещё соединены ребром BC.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • CMU15-451: Undirected DFS and Biconnected Components

    Прочитаны определение блоков и DFS со стеком рёбер, pop до базового ребра при low[child]≥tin[parent]. Собственный граф двух треугольников с мостом разбирается на блоки; основной SQLтекст о распознавании отдельной точки сочленения не повторяется как worked.

Новое ребро сливает путь блоков двусвязности

После добавления ребра не всегда нужно заново вычислять все блоки вершинной двусвязности. Дерево блоков показывает точную область изменения: сливаются блоки на единственном пути между концами нового ребра. Точка сочленения на этом пути может сохраниться, если к ней прикреплена внешняя ветвь.

Перед началом: Блоки вершинной двусвязности; Дерево блоков и точек сочленения.

Изменение описывается в дереве, а не только в исходном графе

Работаем с простым неориентированным графом и добавляем отсутствующее ребро между различными вершинами одной связной компоненты. Его блоковая структура представляется двудольным деревом: одни узлы соответствуют блокам, другие — точкам сочленения. Мост удобно считать отдельным двухвершинным блоком. Вершина, не являющаяся точкой сочленения, принадлежит одному блоку.

Если оба конца уже лежат в одном блоке, нового объединения блоков не происходит. Если они принадлежат разным блокам, в дереве имеется единственный соединяющий путь. Новый обход через добавленное ребро замыкает именно последовательность блоков этого пути, создавая один увеличенный блок.

Внешние ветви не входят в новое слияние

Чтобы попасть в блоковую ветвь вне соединяющего пути и затем выйти из неё, пришлось бы дважды пройти её прикрепляющую точку сочленения. Поэтому простая циклическая связь между концами нового ребра не может поглотить такую ветвь. Внутренние блоки пути объединяются, а остальные блоки сохраняются.

Точка сочленения на пути теряет разделяющую роль между объединёнными блоками. Но если у неё были другие инцидентные блоки, она по-прежнему отделяет их от новой большой части. Значит, утверждение «все точки сочленения пути исчезают» неверно. Нужно сначала убрать внутренние связи сливаемой цепочки, затем проверить оставшиеся ветви.

Предпосылки выделяют другие случаи добавления

Если концы находятся в разных связных компонентах, новое ребро становится мостом: старый путь между ними отсутствовал, и замкнуть цикл нечем. Тогда блоковые деревья соединяются, а не сливаются вдоль существующего пути. Петля или повтор уже имеющегося ребра также относится к другой постановке и здесь не добавляется.

Этот локальный анализ объясняет корректность обновления, но не является заявлением оптимальной сложности полноценной динамической структуры. Для маленького примера результат можно проверить статическим пересчётом всех точек сочленения после добавления. Такая независимая проверка должна совпасть с предсказанием по блоковому дереву.

Одна точка исчезает, другая сохраняет внешнюю ветвь

Условие. Граф состоит из треугольников abc,cde,efg,hij и моста eh. Добавьте ребро bf. Укажите новые блоки и точки сочленения, сравнив их с исходными.

  1. Исходные блоки: {a,b,c}, {c,d,e}, {e,f,g}, {e,h}, {h,i,j}. Точки сочленения равны c,e,h.
  2. Путь между блоками концов b и f проходит через {a,b,c}, точку c, {c,d,e}, точку e и {e,f,g}. Мост eh и треугольник hij находятся вне этого пути.
  3. После добавления bf первые три блока объединяются в один блок {a,b,c,d,e,f,g}. Точка c больше не разделяет его части и перестаёт быть точкой сочленения.
  4. Точка e сохраняется: её удаление по-прежнему отделяет ветвь h,i,j от остальных вершин. Точка h также остаётся, поскольку отделяет i,j от e и большого блока.
  5. Итоговые блоки равны {a,b,c,d,e,f,g}, {e,h}, {h,i,j}. Прямое удаление каждой вершины и подсчёт компонент подтверждают, что точек сочленения стало две: e,h.

Ответ. Слились ровно три блока соединяющего пути. Исчезла точка сочленения c; e и h сохранились из-за внешней ветви.

Проверка. Независимый перебор максимальных двусвязных подмножеств и статический пересчёт компонент после удаления вершин проверяют и новые блоки, и оставшиеся точки сочленения.

Где легко ошибиться. Не удаляйте из дерева все точки сочленения, встреченные на сливаемом пути. Внешние инцидентные блоки могут сохранять их разделяющую роль.

Проверьте понимание

Какие точки сочленения останутся после добавления bf?

Вопросы к этой главе

Почему мост eh не слился с большим блоком?

Он лежит в боковой ветви, не соединяющей b и f. Новое ребро не создаёт обхода из этой ветви к большой части в обход её прикрепления e.

Что изменится при добавлении ребра между разными компонентами?

Такое ребро не замыкает старый путь и является мостом. Нужно соединить два блоковых дерева через новый блок, а не выполнять описанное слияние пути.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Westbrook, Tarjan: online biconnected components

    Университетская аннотация исследования о поддержке мостовых и вершинно-двусвязных компонент при добавлениях. Локальное правило пути блокового дерева и десятивершинный пример обоснованы отдельно; оценки сложности полного алгоритма статьи здесь не используются.

Ушное разложение служит сертификатом двусвязности

Устойчивый к удалению вершины граф можно описывать не только результатом DFS с low. Другое свидетельство строит его из цикла последовательным добавлением открытых ушей: путей с двумя разными старыми концами и новыми внутренними вершинами. Каждое такое расширение сохраняет двусвязность. Разложение объясняет, откуда берутся обходные связи, а не только помечает уязвимые вершины.

Перед началом: Точка сочленения и удаление вершины; Простой путь и цикл.

Оба конца уха должны быть разными старыми вершинами

Конечный простой неориентированный граф хотя бы из трёх вершин; двусвязность означает связность после удаления любой одной вершины.

Начинаем с цикла. Каждое следующее открытое ухо является простым путём, оба конца которого уже входят в построенный подграф, а все внутренние вершины ещё не использованы. Концы различны. Ухо длины одно допустимо как новое ребро между старыми вершинами, если этого ребра раньше не было.

Рёбра разложения должны в сумме дать весь исходный граф без повторов. Если построен только двусвязный остовный подграф, оставшиеся рёбра можно добавить одношаговыми ушами. В отличие от ориентированного случая здесь речь о вершинной двусвязности; цикл, прикреплённый одной общей вершиной, не является открытым ухом.

Добавление уха сохраняет связность после любого удаления

Предположим, старый подграф двусвязен. Если удалить старую вершину, отличную от концов нового уха, старый остаток связан, а ухо остаётся присоединённым обоими концами. Если удалить один конец, оставшаяся часть уха всё ещё соединяется со старым графом через второй конец. Если удалить внутреннюю вершину уха, две его оставшиеся части присоединяются к двум концам старого связного графа.

Эти случаи охватывают любое одно удаление и доказывают сохранение свойства. Базовый цикл двусвязен, поэтому по индукции корректное разложение является достаточным сертификатом. Существенно, что концы разные: при единственной точке прикрепления её удаление отделило бы новые внутренние вершины.

Обратное утверждение даёт способ наращивания

Теорема об ушном разложении утверждает и необходимость: двусвязный граф допускает такое построение, начиная с любого его цикла. Интуиция следующая: пока не включены все вершины, внешняя часть не может прикрепляться к построенной только через одну вершину, иначе та была бы точкой сочленения. Поэтому можно найти внешний путь между двумя разными старыми точками.

Это характеристика всего графа, а не подсчёт блоков. Для графа из нескольких блоков один общий начальный цикл не позволит пересечь точку сочленения открытым ухом. В маленьком примере сертификат проверяют по спискам вершин и рёбер, затем независимо удаляют каждую вершину и проверяют связность оставшегося графа.

Квадрат, два новых пути и короткая хорда

Условие. Граф задан циклом a—b—c—d—a, путём b—e—f—d, путём e—g—c и дополнительным ребром a—f. Предъявите открытое ушное разложение и объясните двусвязность.

  1. Берём начальный цикл a,b,c,d,a. Он содержит четыре разных вершины и четыре ребра. Удаление любой одной его вершины оставляет связный путь.
  2. Добавляем ухо b,e,f,d: концы b,d уже старые и различны, внутренние e,f новые. Полученный шестивершинный подграф остаётся двусвязным по разбору случаев удаления.
  3. Следующее ухо e,g,c имеет старые концы e,c и новую внутреннюю вершину g. Важно добавлять его после первого: до появления e указанный порядок не был бы корректным разложением.
  4. Последним добавляем одношаговое ухо a,f. Оба конца уже есть, внутренних вершин нет. Все десять рёбер исходного графа распределены по четырём частям без повторов; весь граф двусвязен.

Ответ. Разложение: цикл abcd, затем пути befd, egc и ребро af. Оно является сертификатом двусвязности семивершинного графа.

Проверка. Независимые семь проверок удаления вершины оставляют связный граф. Для контраста два треугольника a,b,c и c,d,e имеют общую точку c: её удаление даёт две компоненты, поэтому открытого ушного разложения всего такого графа нет.

Где легко ошибиться. Не разрешайте новому уху возвращаться в тот же старый конец. Закрытое прикрепление через одну вершину может сохранить отсутствие мостов, но создаёт точку сочленения.

Проверьте понимание

Сколько точек сочленения имеет граф с разложением abcd, befd, egc, af из разобранного примера?

Вопросы к этой главе

Почему разрешено ухо без внутренних вершин?

Это способ добавить ещё не использованную хорду между двумя уже построенными вершинами. Связность после удаления оно не ухудшает и позволяет включить все рёбра исходного графа.

Достаточно ли отсутствия мостов для такого открытого разложения?

Нет. У двух треугольников с общей вершиной мостов нет, но общая вершина является точкой сочленения. Открытое разложение характеризует именно вершинную двусвязность.

Сверить определения и условия

Объяснение и задачи написаны для erudeet. Эти источники используются для проверки понятий и границ модели.

  • Jordán, Zhang — Compressed frameworks, §3.1, Theorem 8

    Определение открытого ушного разложения и характеристика двусвязности. Доказательство сохранения при удалении и семивершинный сертификат подготовлены отдельно; задачи жёсткости из остальной статьи не используются.

Источники и работа с материалом

Объяснение, примеры и вопросы написаны для erudeet. Факты и определения сверены по источникам ниже; это ссылки для самостоятельной проверки.

Продолжить разбираться