Является ли каждый мост в графе ребром в дереве поиска в глубину?

Вопрос из книги алгоритмов Скиены:

Предположим, что G — связный неориентированный граф. Ребро e, удаление которого разъединяет граф называется мостом. Должен ли каждый мост e быть ребром в дереве поиска в глубину графа G?

Мое решение на данный момент (нужны предложения):

Я думаю, что мост — это ребро, конечная вершина которого является отрезанным узлом, потому что удаление отрезанного узла разъединяет граф, поэтому удаление этого ребра также отсоединит граф. Ребра в дереве поиска DFS — это ребра дерева и задние ребра, и только ребра дерева могут быть обрезанными ребрами (или мостами), поскольку удаление заднего ребра не отключает граф.

5
задан Alex Shesterov 15 February 2015 в 21:30
поделиться