График, в котором дерево BFS и дерево DFS различны для каждого узла

Question

У меня есть проблема с домашним заданием:

Учитывая неориентированный связный граф G = (V, E).Найдите необходимое и достаточное условие для G, чтобы можно было упорядочить списки смежности (соседей) каждого узла так, чтобы для каждого узла v дерево BFS и дерево DFS из v были разными.Разработайте алгоритм, который проверяет это условие.

Что это за вопрос?

Кажется, мне нужно найти условие G, что существует хотя бы один порядок соседей, который будетсделать деревья разными?

Answer 1

График должен содержать цикл.

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

Достаточно: предположим, что граф имеет цикл.Необходимо рассмотреть несколько случаев:

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

2. , если корень поиска не находится в цикле, рассмотримпервая вершина, принадлежащая циклу, с которым сталкиваются DFS и BFS.Если DFS и BFS сначала сталкиваются с разными элементами, они не могут привести к одинаковым деревьям.Если они встречают одну и ту же вершину, принадлежащую циклу, то по тем же рассуждениям в (1) поддеревья будут различаться.

Чтобы проверить это условие, выполните поиск DFS излюбой вершины и верните true, если вы встретите уже отмеченную вершину, и false в противном случае.