1. 概要

このチュートリアルでは、最小スパニングツリーと、グラフ内の最小スパニングツリーの総数を見つける方法について説明します。

2. スパニングツリーの定義

スパニングツリーの正式な定義から始めましょう。 次に、それに基づいて最小スパニングツリーを定義します。

特定のグラフについて 、スパニングツリーはのサブセットとして定義できます  のすべての頂点をカバーします エッジの数を最小限に抑えます.

これをさらに単純化してみましょう。 頂点セットとエッジセットを持つグラフがあるとします。 上のスパニングツリーは、whereと。のサブセットです。 したがって、スパニングツリーには、指定されたグラフのすべての頂点が含まれますが、すべてのエッジは含まれません。

また、スパニングツリーは特定のグラフのすべての頂点をカバーしているため、切断できないことに注意してください。 一般的なプロパティにより、スパニングツリーにはサイクルを含めることはできません。

最小全域木（MST）は、無向加重グラフで定義できます。 MSTは、スパニングツリーの同じ定義に従います。 ここでの唯一の落とし穴は、選択したエッジの合計エッジ重みが最小になるように、特定のグラフのすべての頂点をカバーするために最小数のエッジを選択する必要があることです。

それでは、を使ってグラフを試してみましょう。 スパニングツリーと同様に、最小スパニングツリーにもグラフのすべての頂点が含まれます。 したがって、。 のエッジセットは、目的関数を持つのサブセットです。

ここで、は最小全域木のエッジの総数を示します。 目的関数は、のすべてのエッジの重みの合計を示し、他のすべてのスパニングツリーの中で最小である必要があります。

3. いくつかの例

このセクションでは、グラフを作成し、スパニングツリーと関連する最小スパニングツリーを作成して、概念をより明確に理解しましょう。

まず、無向の重み付きグラフを見てみましょう。

ここでは、無向の重み付きグラフを使用しました。 グラフから、スパニングツリーの定義に従っていくつかのスパニングツリーを構築します。

また、スパニングツリーを構築するときは、エッジの重みを気にしないことに注意する必要があります。

ここでは、グラフから4つのスパニングツリーを構築しました。 スパニングツリーのそれぞれは、グラフのすべての頂点をカバーし、サイクルを持っているものはありません。

次に、グラフの最小全域木を見つける方法について説明します。 したがって、定義によれば、最小スパニングツリーは、グラフ内の他のすべてのスパニングツリーの中で最小のエッジ重みを持つスパニングツリーです。

最小スパニングツリーを見つけるには、各スパニングツリーのエッジの重みの合計を計算する必要があります。 のエッジの重みの合計はとです。 したがって、他のスパニングツリーの中でエッジの重みが最小になります。 したがって、 は、グラフ。の最小全域木です。

4. プロパティ

スパニングツリーのいくつかのプロパティをリストアップしましょう。 最小スパニングツリーはスパニングツリーでもあるため、これらのプロパティは最小スパニングツリーにも当てはまります。

スパニングツリーでは、エッジの数は常にになります。

たとえば、スパニングツリーとをもう一度見てみましょう。 元のグラフには頂点があり、各スパニングツリーには4つのエッジが含まれています。

スパニングツリーには、ループまたはサイクルは含まれていません。

スパニングツリーは表示されず、ループやサイクルが含まれています。

スパニングツリーからいずれかのエッジを削除すると、切断になります。

スパニングツリーについて考えてみましょう。 いずれかのエッジを削除すると、切断されます。

スパニングツリーに1つのエッジを追加すると、サイクルが作成されます。

ここでも、スパニングツリーを検討しています。 新しいエッジ、たとえばエッジまたはを追加すると、でサイクルが作成されます。

5. MSTの総数

このセクションでは、グラフ内の最小全域木の総数を見つけるための2つのアルゴリズムについて説明します。

5.1. グラフが完全グラフの場合

与えられたグラフが完成している場合、スパニングツリーの総数を見つけることは、異なるラベルを持つツリーを数えることと同じです。 ケイリーの公式を使用して、この問題を解決できます。 ケイリーの公式によると、頂点を持つグラフは、異なるラベルの付いたツリーを持つことができます。

したがって、完全グラフ内のスパニングツリーの総数はに等しいと言えます。

ここで、すべてのスパニングツリーの中から最小スパニングツリーを見つけるために、各スパニングツリーの合計エッジ重みを計算する必要があります。 最小スパニングツリーは、すべてのスパニングツリーの中でエッジの重みが最小のスパニングツリーです。

次に、擬似コードを見てみましょう。

ここで、変数はグラフ内のスパニングツリーの総数を示します。 変数は、スパニングツリーのエッジリストとその重みを格納する配列です。 次に、各スパニングツリーのエッジの重みの合計を計算し、に格納しました。 の最小値は、最小スパニングツリーに対応します。

最後に、変数を使用して、グラフ内の最小全域木の総数を示します。

5.2. グラフが完成していないとき

与えられたグラフが完全でない場合は、行列ツリーアルゴリズムを使用して、最小全域木の総数を見つけることができます。

最初に擬似コードを見てから、手順について詳しく説明します。

アルゴリズムの最初のステップは、与えられたグラフから隣接行列を作成することです。ここで、は隣接行列を示し、は行列の次元です。 隣接行列では、エッジの重みは考慮されないことに注意してください。

次のステップは、グラフから次数行列を作成することです。 隣接行列から次数行列を作成できます。 すべての対角要素をグラフの頂点の次数に置き換え、他のすべての要素をゼロに置き換える必要があります。 変数は、グラフに対応する次数行列を示します。 ここでも、エッジの重みは考慮していません。

ここで、次数行列から隣接行列を差し引くことにより、ラプラシアン行列を計算します。 変数は、指定されたグラフのラプラシアン行列を表します。

与えられたグラフでスパニングツリーの総数を見つけるには、ラプラシアン行列の要素の補因子を計算する必要があります。この数は、グラフのスパニングツリーの総数に相当します。 行列の計算補因子の一般式は次のとおりです。、ここで、は行列のインデックスです。

このアルゴリズムでは、変数で表される値との補因子を計算することにしました。 の任意の値を選択できます。

次に、各スパニングツリーのエッジリストとその重みをに格納します。 前のアルゴリズムと同様に、で示される各スパニングツリーのエッジの重みの合計を計算します。 並行して、重みの合計もリストに格納します。 の最小エントリは最小スパニングツリーです。

最小全域木の総数を見つけるために、で最小のエントリの出現を見つけます。 変数は、与えられたグラフの最小全域木の総数を示します。

6. グラフでのアルゴリズムの実行

このセクションでは、2つのグラフを取り上げます。1つは完全グラフであり、もう1つは完全グラフではありません。 両方のグラフについて、アルゴリズムを実行し、指定されたグラフに存在する最小スパニングツリーの数を見つけます。

まず、完全な無向加重グラフを見てみましょう。

頂点を含むグラフを作成しました。 私たちのアルゴリズムによると、のスパニングツリーの総数は次のようになります。 スパニングツリーをリストアップしましょう：

ここで、スパニングツリーの中から最小スパニングツリーを見つけるために、各スパニングツリーの重みを計算する必要があります：、、。 スパニングツリーは、すべてのスパニングツリーの中で最小の重みを持っていることがわかります。 したがって、の最小全域木の数はです。

次に、完全グラフではないグラフを見てみましょう。

ここでは、頂点を含むグラフを作成しています。 ここで、最初のステップは、エッジの重みを使用せずにの隣接行列を作成することです。

   

次に、グラフに対応する次数行列を作成します。 ここでも、エッジの重みは考慮しません。

   

次に、次数行列から隣接行列を減算して、ラプラシアン行列を作成します。

   

ラプラシアン行列が完成しました。 次のステップは、ラプラシアン行列から正の補因子のいずれかを計算することです。 一般式は次のとおりです。 とを計算してみましょう：

したがって、グラフ内のスパニングツリーの数は次のとおりです。

ここでは、各スパニングツリーのエッジの重みの合計を計算します。 スパニングツリーの重みは次のとおりです。

明らかに、回転する木の中で最小のエッジの重みはです。 ここで、アルゴリズムで、スパニングツリーのすべての重みが格納されているリスト内の最小のエッジ重みの発生をカウントする変数を定義しました。 でエッジの重みが3回発生することがわかります。これは、に対応します。

したがって、グラフ にアルゴリズムを適用したところ、のスパニングツリーの総数はであり、最小スパニングツリーの総数であることがわかりました。 is。

7. 時間計算量分析

完全グラフの場合、アルゴリズムの時間計算量は、各スパニングツリーのエッジの重みの合計を計算するループによって異なります。 ループは、グラフ内のすべての頂点に対して実行されます。 したがって、アルゴリズムの時間計算量はになります。

与えられたグラフが完全でない場合は、マトリックスツリーアルゴリズムを提示しました。 すべての操作の中で、最も費用のかかる操作は、行列の決定を見つけることです。 時間がかかる。 したがって、アルゴリズムの合計時間計算量はになります。

8. MSTのアプリケーション

最小スパニングツリーの重要なアプリケーションは、マップ上のパスを見つけることです。

最小スパニングツリーは、電気通信ネットワーク、給水ネットワーク、電力網などのネットワークを設計するために使用されます。

クラスター分析、画像セグメンテーション、手書き認識などの実用的なアプリケーションはすべて、最小スパニングツリーの概念を使用します。

9. 結論

このチュートリアルでは、グラフ内のスパニングツリーの総数と最小スパニングツリーを見つける方法について説明しました。

2つの異なるケースに対して2つのアルゴリズムを提示し、各ステップを詳細に説明しました。 提示されたアルゴリズムを検証するために、2つのサンプルグラフでアルゴリズムを実行してテストしました。