ВОРОТА | ВОРОТА КС 2021 | Набор 1 | Вопрос 51

Точка сочленения в связном графе — это такая вершина, что удаление вершины и инцидентных с ней ребер разъединяет граф на две или более компоненты связности.

Пусть T — дерево в глубину, полученное в результате выполнения поиска в глубину в связном неориентированном графе G.

Какой из следующих вариантов правильный?
(A) Корень Т никогда не может быть точкой артикуляции в G.
(B) Корень T является точкой артикуляции в G тогда и только тогда, когда он имеет 2 или более потомков.
(C) Лист T может быть точкой артикуляции в G.
(D) Если u — точка артикуляции в G, такая, что x — предок u в T, а y — потомок u в T, то все пути от x до y в G должны проходить через u.

Ответ: (Б) (Д)
Объяснение: Как найти все точки артикуляции?
Подход на основе DFS:
Мы можем доказать следующие свойства:

• Корень DFS-дерева является точкой сочленения тогда и только тогда, когда у него есть по крайней мере два потомка.
  
• Лист DFS-дерева никогда не является точкой артикуляции.
  

D неверно, потому что не обязательно иметь путь только через точку артикуляции. В графе G также может быть прямой путь от x к y.

Тест на этот вопрос