graph-theory - トーナメント グラフの支配的なセット

Question

トーナメント グラフの支配的なセットを見つけるアルゴリズムを作成しています。有向グラフの最小全域木は、グラフの支配集合と同等ですか? 言い換えれば、トーナメント グラフの最小の MST を (すべての頂点を反復することによって) 見つけた場合、これはグラフの支配的なセットと同等であると言えますか?

Answer 1

このウィキペディアの記事では、支配集合を見つけることとスパニングツリーを見つけることの問題は同等であると述べています。スパニングツリーが与えられると、非リーフノードが支配集合を形成し、接続された支配集合が与えられると、そのスパニングツリーの1つとそれに属していない頂点を結合する元のグラフを簡単に取得できます。ただし、最小全域木を見つけることと最小支配集合を見つけることは別の問題です。再び同等だと思いますが、よくわかりません。

Answer 2

いいえ、MSTにはグラフのすべての頂点が含まれ、支配集合には含まれない可能性があるためです。

たとえば、次のグラフを参照してください。http: //en.wikipedia.org/wiki/Tournament _（グラフ_理論） 頂点2と4は、スパニングツリーではなく支配集合を作成します。