algorithm - 線形時間でツリーの最適な頂点カバーを見つける効率的な貪欲なアルゴリズムを与えてください

Question

私はこの問題に取り組もうとしています...以下は1つのアルゴリズムです..私は理解しました..

入力グラフは、他のすべてのノードとの一致度が最も高い頂点を選択します。このノードに付随するエッジを削除します。選択した頂点とそのエッジをセット X に追加します。X を返します。

X は、頂点カバーに必要な頂点の最小セットを返します。この方法は正しいですか? ありがとう

Answer 1

次数が最も高い頂点を選択しても、最適な解が得られるとは限りません。たとえば、7 つの頂点を持つツリーがあり、エッジは次のようにリストされます。

1 2 // (1,2) is connected.
1 3
1 4
2 5
3 6
4 7

最小の頂点カバーは {2,3,4} ですが、貪欲なアプローチに基づいて、最初に {1} を選択し、次に左の 3 つのエッジをカバーするために少なくとも 3 つの頂点を選択します。

実際、ツリーの頂点被覆問題を解決する貪欲なアルゴリズムがあります。つまり、各ステップでリーフを見つけます (入力はツリーであるため、エッジが残っていない限り、常にそのようなリーフを見つけることができます)。頂点カバー セット X への葉の隣接。グラフが空の場合、最小頂点カバーとして X を返します。E = V-1 の場合、複雑さは O(E) であり、線形解であると言えます。