質問: T をノード r をルートとする n ノード ツリーとします。T のすべてのエッジが保護されるように、T のノードにできるだけ少ないガードを配置する必要があります。これら 2 つのノード v の少なくとも 1 つにガードを配置すると、親ノード v とその子 w の間のエッジが保護されます。 、w。問題の最適解を見つけるための O(n) 時間アルゴリズムを与えてください。
私のアプローチは、ルートからポスト オーダー トラバーサルを行い、そのノードがリーフである場合を除いて、ガードされていないエッジの一部であるノードにガードを配置することでした...しかし、すべてのノードが配置されている場合、このアルゴリズムは機能しません。私のアルゴリズムは、チェーンの端を除くすべてのノードにガードを配置するためです。
私はオンラインで見て、DPソリューションをチェックアウトしましたが、これは私には理にかなっていますが、ツリーの頂点カバーを見つけるための貪欲なアルゴリズムがあるかどうか疑問に思っていました