トーナメントグラフのセットの支配

Question

トーナメントグラフの支配的なセットを見つけるアルゴリズムを書いています。有向グラフの最小全域木は、グラフの支配的なセットと同等ですか？つまり、トーナメントグラフの最小のMSTを（すべての頂点を反復処理して）見つけた場合、これはグラフの支配的なセットと同等であると言えますか？

Answer 1

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

Answer 2

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

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