Я не понимаю, как этот алгоритм скажет мне, является ли граф двоичным.

Question

Я делаю некоторую практику для предстоящего интервью, и практический вопрос, который я нашел, требует алгоритма O (V + E), чтобы определить, График двоичный. This страница из Принстона говорит, что граф двоичный, если он не имеет шарнирных вершин, где вершина сочленения - это вершина, удаление которой увеличит количество подключенных компонентов (так как битконфигурированный граф должен иметь одну связанную компоненту).

Одним из распространенных решений этой проблемы является создание DFS с дополнительным отслеживанием, чтобы увидеть, являются ли какие-либо из вершин вершинами сочленения. This страница говорит, что вершина является артикуляция вершиной, если

• V является корневым узлом по крайней мере, 2 детям ИЛИ
• V есть ребенок, который не может достичь предка V

Однако , условие для корневых узлов для меня не имеет смысла. Ниже приведен пример биконфинированного графика:

Если мы выберем любой из узлов, являющихся корнем, они ВСЕ имеют 2 или более дочерних элементов, поэтому это была бы точка сочленения, что сделало бы граф не двоичным. Это общий алгоритм поиска подключенных компонентов, поэтому предположим, что я что-то не понял. Что мне нужно проверить для корневого узла, чтобы увидеть, является ли граф двоичным?

Answer 1

Вы должны делать поиск в глубине, а это значит, что дерево DFS всегда выглядит

1 4 
| | 
2---3 

, потому что вы не можете исследовать 1--4 ссылки, пока вы не сделали, исследуя все, что может быть достигнуто от 2, не пройдя 1, и вы не добавите 1--4, потому что он делает цикл с краями дерева. Ни один узел в этом дереве не имеет двоих детей (1 - это корень).