algorithm - ツリー内のノードの接続

Question

架空の質問です。木 T と、T 内のノードのペア (x、y) のリストが与えられたとします。T 内の各エッジを最大 1 回使用して、同時接続 (x を y に接続) できるペアの数を尋ねられます。 .

どうやってそれをしますか？

Answer 1

ツリーの NP 困難ではありません。たとえば、次のことができます。

1. ツリーを任意にルート化します。

2. 各頂点 v について、v のサブツリーに限定される最適解を計算します。

3. さらに、各 v について、v の親エッジを含む各パス p について、パス p を除く v のサブツリーに限定される最適解を計算します。

(2) と (3) は、v のサブツリー内の小さな問題の解を使用して計算できます。

ステップ 1、2、および 3 を調べて、自分で再帰を計算する方がおそらく簡単ですが、アイデアを提供するために、(2) はいくつかの解の最大値を取ることによって計算できます。 v の子 (つまり、子ごとにステップ 2 で生成されたソリューションの合計)、および v を含むパスごとに 1 つと、他の子のステップ 2 のソリューション (これには基本的に、生成された 1 つまたは 2 つのソリューションの合計が含まれます) v の子のステップ 3 と、他の子のステップ 2 で生成された解の合計)。