Как проверить, имеет ли дерево идеальное совпадение по линейному времени?

Question

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

Это из Алгоритмы С. Дасгупты, и я просто не могу решить эту проблему. Я знаю, что мне нужно каким-то образом использовать жадный подход, но я просто не могу понять это. Помогите?

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

Алгоритм должен быть линейным во всем. O (V + E) в порядке.

Answer 1

Я думаю, у меня есть решение. Так как мы знаем, что граф является деревом , мы знаем о существовании листовых узлов, узлов с одним ребром и без дочерних. Чтобы этот узел был включен в идеальное соответствие, этот край ДОЛЖЕН существовать в конечном решении.

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

Answer 2

В случае «графика», Первым шагом проблемы должен быть поиск подключенных компонентов.

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

Затем можно найти идеальное соответствие для каждого подключенного компонента.

Answer 3

Я думаю, что это упрощенная задача поиска гамильтонова пути в графе: http://en.wikipedia.org/wiki/Hamiltonian_path

http://en.wikipedia.org/wiki/Hamiltonian_path_problem

Я думаю, что в Интернете есть много решений этой проблемы, но обычно нахождение цикла Гамильтона является проблемой NP.

Answer 4

Линейный в что ? Линейный по количеству ребер, сохраните ребра как упорядоченный список инцидентности, то есть каждое ребро ( v _i , v _j ) в некотором общем порядке. Затем вы можете сравнить два списка в O ( n ) ребер.