1. 概要

このチュートリアルでは、グラフ理論の2つの概念、最小スパニングツリーと最小ボトルネックスパニングツリーを紹介します。定義について例を挙げて説明します。

最後に、2つのツリー構造のコアの違いについて説明します。

2. 最小スパニングツリー（MST）の定義

無向、接続、加重グラフが与えられます。 スパニングツリーグラフは、のすべての頂点を含むツリーです。 したがって、。 さらに、のすべてのエッジもに存在する必要があります。 したがって、 。

入力グラフのスパニングツリーは一意ではありません。さらに、特定のグラフに対して、さまざまなスパニングツリーを見つけることができます。 スパニングツリーのコストは、ツリーに存在するすべてのエッジの合計です。 したがって、エッジの重みに基づいて、特定のグラフのスパニングツリーのコストは異なる可能性があります。

これで、最小スパニングツリーの定義について説明する準備が整いました。 最小スパニングツリーは、特定のグラフで可能なすべてのスパニングツリーの中で最小のコストを持つスパニングツリーです。

さまざまな実際のアプリケーションで、画像セグメンテーション、手書きの認識、リアルタイム（ビデオ）での顔追跡などの最小スパニングツリーが使用されます[ X195X]、クラスターの分析、ネットワーク設計。

2.1. 例

グラフから最小全域木を見つける方法の例を見てみましょう：

この例では、入力グラフは頂点を持つ完全グラフです。 次に、グラフで可能なすべてのスパニングツリーを見つけましょう。

入力グラフが完全に接続されているため、可能なスパニングツリーの総数はです。 ここで、はグラフ内の頂点の総数を示します。 したがって、グラフのスパニングツリーを生成しました。

スパニングツリーのコストはです。 したがって、のすべての可能な全域木の中で、最小のコストがあることがわかります。 したがって、はグラフの最小全域木です。

3. 最小ボトルネックスパニングツリー（MBST）の定義

スパニングツリーのボトルネックは、最大の重みを持つエッジとして定義されます。 したがって、無向、接続、および加重グラフの最小ボトルネックスパニングツリー は、のすべての可能なスパニングツリーの中で最大加重エッジが最小であるツリーです。

すでに説明したように、特定のグラフには、複数のスパニングツリーが存在する場合があります。 したがって、スパニングツリーのセットから最小スパニングツリーとして最小コストのスパニングツリーを選択します。 最小スパニングツリーでは、最大コストのエッジがボトルネックエッジです。 最後に、この特定のエッジを含むスパニングツリーは、最小のボトルネックスパニングツリーです。

3.1. 例

無向、接続、加重グラフを見てみましょう :

次に、コストとボトルネックエッジを持つすべてのスパニングツリーをリストアップしましょう。

ここで、グラフに対応する全域木の総数はです。 与えられたグラフからすべての可能なスパニングツリーを見つけることは、最小のボトルネックスパニングツリーを見つける最初のステップです。 次のステップは、すべての可能なスパニングツリーの中から最小スパニングツリーを見つけることです。

のすべての可能なスパニングツリーの中で、最小コストがあります。 したがって、はの最小全域木です。 ボトルネックエッジ、最小スパニングツリーの最大加重エッジを見つける必要があります。

のエッジがボトルネックエッジであることがわかります。これは、の最も高い重みのエッジです。 したがって、エッジを含むすべてのスパニングツリーは、最小のボトルネックスパニングツリーです。 したがって、グラフの、ツリーにまたがる最小ボトルネックはです。

3.2. MBSTのプロパティ

最小ボトルネックスパニングツリーには、いくつかの興味深い特性があります。 A 最小ボトルネックスパニングツリーは、最小スパニングツリーである場合とそうでない場合があります。の場合、最小ボトルネックスパニングツリーが見つかりました。 のうち、は最小全域木です。 ただし、最小全域木ではありません。 したがって、すべての最小スパニングツリーが最小スパニングツリーであるとは限りません。

MSTは常にMBSTです。MBSTの定義により、ボトルネックエッジはMSTに属している必要があります。 実際、ボトルネックエッジを含むスパニングツリーからMBSTを選択します。

MBSTの総重みは、常に特定のグラフのMSTの総重み以上になります。たとえば、グラフのMSTの重みはです。 一方、のMBSTの重みはとです。

4. MBSTとMSTの違い

これで、MBSTがMSTとどのように異なるかがわかりました。 それらの間のコアの違いについて話しましょう：

5. 結論

この記事では、グラフ理論における2つの非常に近いが異なるグラフの概念、最小スパニングツリー、最小ボトルネックスパニングツリーについて説明しました。 グラフの例を使用して、両方のツリーの定義を示しました。

最後に、それらのコアの違いについて説明しました。