Соединяющие узлы в дереве

Question

гипотетический вопрос. Скажем, у меня есть дерево T и список пар узлов (x, y) в T. Меня спрашивают, сколько пар я могу соединить одновременно (соединить x с y), используя каждое ребро в T не более одного раза ,

Как бы к этому?

Answer 1

Это не сложно для NP-деревьев.Вы можете сделать следующее, например.

1. Произвольно укоренить дерево.

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

3. Кроме того, для каждого v, для каждого пути p, который включает родительское ребро v, вычислить оптимальное решение, которое ограничено поддеревом v, за исключением пути p.

(2) и (3) могут быть вычислены с использованием решений меньших задач в поддереве v.

Вероятно, проще взглянуть на шаги 1, 2 и 3 и самостоятельно определить повторение, но просто для того, чтобы дать вам представление, (2) можно вычислить, приняв максимум несколько решений: однокоторая суммирует решения для дочерних элементов v (т. е. сумму решений, полученных на шаге 2 для каждого дочернего элемента), и по одному для каждого пути, который включает v плюс решения шага 2 для других дочерних элементов (это будет по существу включать суммуодного или двух решений, полученных на шаге 3 для детей v, плюс сумма решений, полученных на шаге 2 для других детей).