ノードを選択した場合、ノードの親ノードを選択する必要があるように、ツリーからK個のノードを選択する方法の数

Question

各ノードに任意の数の子を持つことができるツリーがある場合、この問題を解決しようとしています。私はKノードを選択するためのすべての可能な方法を見つける必要があります。そうすれば、どのノードも親が選択された場合のみ選択されます。

私は試みましたが、解決策を見つけることができませんでした。誰かが私を助けることができますか？基本的なアルゴリズム（擬似コード）で十分です。

Answer 1

DFSを使用してこの問題を解決できます。グラフの頂点を選択することができます。したがって、選択肢から1つの頂点を削除し、別の有効なツリーノードを選択肢に追加することによって、1つの選択肢を別の選択肢に変換できる場合は、2つの頂点/選択間にエッジが存在します。このグラフは接続されているので、DFSによってそれをトラバースできます。私たちは他の頂点を生成するために、開始頂点を

例えば：

input tree:  1    K=3 
      /| \ 
       3 4 5 
       // \ 
       6 7  2 

first solution (preorder traversal): 
     1 
    /| 
    3 4 

consecutive solutions: 
    removing node 3 from selection removing node 4 
     1   1      1 
     |   | \    / \ 
     4   4 5    3  5 
    /
     6 

必要があるので、我々はで開始する有効な選択を必要としています。最も簡単な解決策は、木のプリオーダーを走査して最初のKノードを選択することです。

最初の頂点から、実行時にグラフ全体を生成することができます。
基本的に、各ノードには入力ツリーのサブツリー、つまり選択が含まれています。トラバースするノードから選択します。選択によって表されるサブツリーから任意のリーフを除去することにより、K - 1個のノードを有するサブツリー/選択を得る。この選択は、新しいリーフとなる別のノードをサブツリーに追加することによって、Kノードに完了させることができる。このアプローチは、上記のエッジの定義にも一致します。

ここで、特定の頂点/選択からすべての隣接する頂点を作成する方法を知っています。残りは単なるDFSトラバーサルです。訪問された頂点にマークを付け、すべての隣接頂点を取得し、すべての頂点が訪問されるまでそれらの上でDFSトラバーサルを実行します。