この記事では、スパニング ツリーとミニマム スパニング ツリーについて説明します。ただし、スパニング ツリーに直接進む前に、まずグラフとそのタイプについて簡単に説明します。

グラフ

グラフは、頂点とこれらの頂点を接続するエッジのグループとして定義できます。グラフの種類は次のとおりです。

無向グラフ:無向グラフは、すべてのエッジが特定の方向を指していないグラフです。つまり、一方向ではありません。それらは双方向です。これは、V 頂点のセットと E エッジのセットを備えたグラフとして定義することもできます。各エッジは 2 つの異なる頂点を接続します。接続されたグラフ:接続されたグラフとは、ある頂点から他の頂点までのパスが常に存在するグラフです。いずれかの方向にエッジをたどることによって、他の頂点から任意の頂点に到達できれば、グラフは接続されています。有向グラフ:有向グラフは有向グラフとも呼ばれます。グラフの頂点またはノード間に存在するすべてのエッジが方向を向いているか、定義された方向を持っている場合、グラフは有向グラフ (または有向グラフ) です。

さて、トピックのスパニングツリーに移りましょう。

スパニングツリーとは何ですか?

スパニング ツリーは、無向接続グラフのサブグラフとして定義できます。これには、すべての頂点と可能な限り少ない数のエッジが含まれます。頂点が欠けている場合、それはスパニング ツリーではありません。スパニング ツリーはサイクルを持たないグラフのサブセットであり、切断することもできません。

スパニング ツリーは (n-1) 個のエッジで構成されます。「n」は頂点 (またはノード) の数です。スパニング ツリーのエッジには重みが割り当てられている場合と、割り当てられていない場合があります。指定されたグラフ G から作成されるすべての可能なスパニング ツリーは同じ数の頂点を持ちますが、スパニング ツリー内のエッジの数は、指定されたグラフ内の頂点の数から 1 を引いたものと等しくなります。

完全な無向グラフには次のものがあります。 n^n-2 スパニングツリーの数 n グラフ内の頂点の数です。仮に、 n = 5 の場合、可能なスパニング ツリーの最大数は次のようになります。 5^5-2= 125。

スパニングツリーの応用例

基本的に、スパニング ツリーは、グラフのすべてのノードを接続する最小パスを見つけるために使用されます。スパニング ツリーの一般的なアプリケーションのいくつかを次に示します。

• クラスター分析
• 土木ネットワーク計画
• コンピュータネットワークルーティングプロトコル

ここで、例を使用してスパニング ツリーを理解しましょう。

スパニングツリーの例

グラフが次のようになると仮定します -

上で説明したように、スパニング ツリーにはグラフと同じ数の頂点が含まれます。上のグラフの頂点の数は 5 です。したがって、スパニング ツリーには 5 つの頂点が含まれます。スパニング ツリーのエッジは、グラフの頂点の数から 1 を引いたものと等しくなります。つまり、スパニング ツリーには 4 つのエッジが存在します。

上のグラフから作成される可能性のあるスパニング ツリーの一部を以下に示します。

スパニングツリーのプロパティ

スパニング ツリーのプロパティの一部は次のとおりです。

• 接続されたグラフ G には複数のスパニング ツリーが存在する場合があります。
• スパニング ツリーにはサイクルやループがありません。
• スパニングツリーとは、 最小限の接続で、 したがって、ツリーから 1 つのエッジを削除すると、グラフが切り離されてしまいます。
• スパニングツリーとは、 最大限に非周期的、 したがって、ツリーにエッジを 1 つ追加するとループが作成されます。
• 最大値が存在する可能性があります n^n-2 完全なグラフから作成できるスパニング ツリーの数。
• スパニングツリーには、 n-1 エッジ。「n」はノードの数です。
• グラフが完全なグラフの場合、最大 (e-n+1) 個のエッジを削除することによってスパニング ツリーを構築できます。ここで、「e」はエッジの数、「n」は頂点の数です。

したがって、スパニング ツリーは接続されたグラフ G のサブセットであり、切断されたグラフのスパニング ツリーは存在しません。

最小スパニングツリー

最小スパニング ツリーは、エッジの重みの合計が最小となるスパニング ツリーとして定義できます。スパニング ツリーの重みは、スパニング ツリーのエッジに与えられた重みの合計です。現実の世界では、この重みは距離、交通量、混雑、または任意のランダムな値と考えることができます。

最小スパニングツリーの例

例を使用して最小スパニング ツリーを理解しましょう。

上のグラフのエッジの合計は 16 です。 さて、上のグラフから作成される可能なスパニング ツリーのいくつかは次のとおりです。

したがって、指定された加重グラフに対して上記のスパニング ツリーから選択される最小のスパニング ツリーは次のようになります。

最小スパニングツリーの応用例

最小スパニングツリーの適用は次のようになります。

• 最小スパニング ツリーは、給水ネットワーク、通信ネットワーク、電力網の設計に使用できます。
• マップ内でパスを検索するために使用できます。

最小スパニングツリーのアルゴリズム

以下に示すアルゴリズムを使用して、重み付きグラフから最小スパニング ツリーを見つけることができます。

• プリムのアルゴリズム
• クラスカルのアルゴリズム

上記の両方のアルゴリズムについて簡単に説明します。

プリムのアルゴリズム - これは、空のスパニング ツリーから開始する貪欲なアルゴリズムです。グラフから最小スパニングツリーを見つけるために使用されます。このアルゴリズムは、エッジの重みの合計が最小化されるように、グラフのすべての頂点を含むエッジのサブセットを見つけます。

キャメルケースパイソン

プリムのアルゴリズムの詳細については、以下のリンクをクリックしてください。 https://www.javatpoint.com/prim-algorithm

クラスカルのアルゴリズム - このアルゴリズムは、接続された重み付きグラフの最小スパニング ツリーを見つけるためにも使用されます。クラスカルのアルゴリズムも、全体的な最適化に焦点を当てるのではなく、あらゆる段階で最適な解決策を見つける貪欲なアプローチに従っています。

プリムのアルゴリズムの詳細については、以下のリンクをクリックしてください。 https://www.javatpoint.com/kruskal-algorithm

それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。ここでは、スパニング ツリーとミニマム スパニング ツリーについて、そのプロパティ、例、アプリケーションとともに説明しました。