트리에서 노드 연결

Question

hypotetical question. 내가 나무 T와 T의 노드 쌍 (x, y) 목록을 받았다고 가정 해 봅시다. T에서 각 edge를 최대 한 번 사용하여 simotaneously (y와 x 연결) 할 수있는 쌍의 수를 묻습니다. .

어떻게 생각하나요?

Answer 1

나무에는 NP 어려운 것은 아닙니다. 예를 들어, 다음을 수행 할 수 있습니다.

1. 임의로 트리를 뿌리십시오.

2. 각 정점 v에 대해 v의 하위 트리에만 국한된 최적 해를 계산합니다.

3. 또한 각 v에 대해 v의 모서리를 포함하는 각 경로 p에 대해 경로 p를 제외하고 v의 하위 트리에만 국한되는 최적 해를 계산합니다.

(2) 및 (3)은 v의 서브 트리 내의 더 작은 문제에 대한 해답을 사용하여 계산 될 수있다.

1 단계, 2 단계 및 3 단계를보고 재귀를 직접 계산하는 것이 더 쉽지만 아이디어를 얻으려면 (2) 최대 해를 구하면 계산할 수 있습니다. v의 자녀들을위한 해답 (즉, 각 어린이에 대해 2 단계에서 생성 된 해의 합)과 v를 포함하는 각 경로에 하나 더하기 다른 어린이들에 대한 2 단계 해법 (이것은 본질적으로 하나의 또는 v의 자녀에 대해 3 단계에서 생성 된 두 가지 솔루션과 다른 어린이에 대해 2 단계에서 생성 된 솔루션의 합계).