すべてのカットに弱く接続されたセットがある (あるセットから別のセットへの有向パスが少なくとも 1 つある) 有向グラフで弱く接続されている DAG にまたがる最大の重みを見つけるアルゴリズムはありますか? それともNP難しい問題ですか？このトピックに関する前の質問では、接続が弱いか強いかを指定していませんでした。より正確な。
1404 次
2 に答える
0
あなたの弱い接続状態は、基になる無向グラフが接続されているようです。これは簡単です。Kruskal や Prim など、お気に入りの最小スパニング ツリー アルゴリズムを使用できます。
最小重みの強連結サブグラフは NP 完全です。そのようなサブグラフには少なくとも |V| があることに注意してください。エッジであり、それが正確に |V| を持っていること。ハミルトニアン サイクルである場合に限り、エッジが適用されます。
「ルート」となる頂点を選択し、すべての頂点からサブグラフのルートへのパスが必要になる場合があります。これが「最小スパニング アーボレッセンス」問題です。@matejpavouk が指摘したように、これには Chu、Liu、および Edmonds による二次アルゴリズムがあります。
于 2012-12-27T00:50:08.723 に答える