N 個の頂点を持つ完全なグラフの最小全域木 (MST) の最小数は?
質問する
352 次
1 に答える
2
答えは1だと思います。
ちょうど 1 つの MST を持つ n 個のノードを持つ完全なグラフを作成することができます。これを行うには、1、2、3、...、n とラベル付けされた n 個のノードを持つグラフを作成します。次に、コスト 0 のエッジを 1 から 2、2 から 3、3 から 4、...、n - 1 から n に追加し、コスト 1 のノードのペアを 1 つおきに接続するエッジを追加します。すべてのゼロ コスト エッジを選択すると、このグラフの 1 つの可能なスパニング ツリーが得られます。これは最小スパニング ツリーです。これは、エッジの他の選択肢が選択された場合、コストが少なくとも 1 になるためです。さらに、これはグラフ内の唯一の MST です。エッジの別のセットが選択された場合、そのセットには少なくともコスト 1 のエッジが少なくとも 1 つ含まれている必要があるため、合計 MST のコストは少なくとも 1 になります。
お役に立てれば！
于 2012-12-21T21:47:20.163 に答える