[解決済み] 最小ボトルネックスパニングツリーと最小スパニングツリーはどう違うのですか？

質問

重み付きグラフの最小ボトルネックスパニングツリー G のスパニングツリーです。 G このとき、スパニングツリー内の任意の辺の最大重みが最小になるようにします。MBSTは必ずしもMST(minimum spanning tree)である必要はない。

これらの文が意味を持つ例を挙げてください。

どのように解決するのですか？

をご覧ください。 WikipediaのMSTの例 を参考にしてください。

スパニングツリーにおけるボトルネックとは、そのツリーにおける最大重量のエッジのことである。1本の木に複数のボトルネックが存在することもある（もちろんすべて同じ重さ）。ウィキペディアのMSTでは、ウェイト8のボトルネックが2つある。

ここで、与えられたグラフの最小木（複数のMSTがあり、もちろんすべての辺の総重量が同じ）をとり、最大辺の重さをBと呼ぶ。この例では、B = 8。

B = 8をボトルネックとする木はMBSTである。しかし、MSTでない場合もある（エッジの総重量が最良より大きいから）。

そこで、WikipediaのMSTを修正（いくつかのエッジを追加/削除）し、次のようにします。

1. スパニングツリーのままであり
2. は、まだ、weight >8を使用していません。
3. エッジの総重量を増やすと

例えば、WikipediaのMSTの左側のサブツリー（重み{2, 2, 3}で構成）を{2, 3, 6}に変更し、ボトルネックの8を変えずにエッジの総重量を4増やします。 ビンゴ、MSTでないMBSTができました。