algorithm - 最小ボトルネックスパニングツリーは、最小スパニングツリーとどのように異なりますか？

Question

重み付きグラフGの最小ボトルネックスパニングツリーは、スパニングツリー内の任意のエッジの最大重みを最小化するようなGのスパニングツリーです。MBSTは、必ずしもMST（最小スパニングツリー）である必要はありません。

これらのステートメントが意味をなす例を挙げてください。

Answer 1

参考のためにウィキペディアのMSTの例を見てください。

スパニングツリーのボトルネックは、そのツリーの最大ウェイトエッジです。スパニングツリーには、いくつかのボトルネック（もちろんすべて同じ重み）が存在する可能性があります。ウィキペディアMSTには、重み8の2つのボトルネックがあります。

ここで、特定のグラフの最小スパニングツリー（複数のMSTが存在する場合があり、すべて同じ合計エッジウェイトを持つ場合があります）を取得し、最大エッジウェイトをBと呼びます。この例ではB=8です。

B=8のボトルネックもあるスパニングツリーはMBSTです。ただし、MSTではない場合があります（エッジの総重みが可能な限り大きいため）。

したがって、ウィキペディアMSTを取得し、次のように変更します（いくつかのエッジを追加/削除します）。

1. それはスパニングツリーのままであり、
2. それでも8を超える重みは使用しませんが
3. エッジの総重量を増やします

たとえば、ウィキペディアMSTの「左側」のサブツリー（重み{2、2、3}で構成される）だけを{2、3、6}に変更します。これにより、のボトルネックを変更せずに、エッジの合計重みを4増やすことができます。 8.ビンゴ、MSTではないMBSTを作成しました。

Answer 2

あなたの質問に答える前に、ここで使用されているいくつかの用語を定義しましょう...

1）スパニングツリー：特定のグラフのスパニングツリーは、そのグラフのすべての頂点をカバーするツリーです。

2）最小スパニングツリー（MST）：特定のグラフのMSTは、そのグラフのすべての可能なスパニングツリーの中で長さが最小のスパニングツリーです。より明確に、与えられたグラフについて、すべての可能な全域木（非常に大きくなる可能性があります）をリストし、エッジの重みの合計が最小であるものを選択します。

3）最小ボトルネックスパニングツリー（MBST）：特定のグラフのMBSTは、可能なすべてのスパニングツリーの中で最大エッジ重みが最小であるスパニングツリーです。より明確に、特定のグラフについて、すべての可能なスパニングツリーと各スパニングツリーの最大エッジ重みをリストします。これらの中から、最大エッジ重みが最小であるスパニングツリーを選択します。

次に、4ノードのグラフで次の図を見てみましょう...

グラフ-Aは与えられた元のグラフです。このグラフで可能なすべてのスパニングツリーをリストし、エッジの重みの合計が最小であるものを選択すると、Graph-Bが得られます。したがって、Graph-Bは最小スパニングツリー（MST）です。その総重量は1+2 + 3=6であることに注意してください。

ここで、最大エッジ重みが最小のスパニングツリー（つまりMBST）を選択すると、Graph-B（または）Graph-Cのいずれかを選択することになります。これらのスパニングツリーは両方とも最大エッジウェイト3を持ち、これはすべての可能なスパニングツリーの中で最小であることに注意してください。

Graph-BとGraph-Cから、Graph-CはMBSTですが、MSTではないことがわかります。その総重量は1+3 + 3 = 7であるため、これはGraph-Bで描画されたMSTの総重量（つまり6）よりも大きくなります。

したがって、MBSTは必ずしも特定のグラフのMSTである必要はありません。ただし、MSTはMBSTである必要があります。