この記事では、スパニング ツリーとミニマム スパニング ツリーについて説明します。ただし、スパニング ツリーに直接進む前に、まずグラフとそのタイプについて簡単に説明します。
グラフ
グラフは、頂点とこれらの頂点を接続するエッジのグループとして定義できます。グラフの種類は次のとおりです。
さて、トピックのスパニングツリーに移りましょう。
スパニングツリーとは何ですか?
スパニング ツリーは、無向接続グラフのサブグラフとして定義できます。これには、すべての頂点と可能な限り少ない数のエッジが含まれます。頂点が欠けている場合、それはスパニング ツリーではありません。スパニング ツリーはサイクルを持たないグラフのサブセットであり、切断することもできません。
スパニング ツリーは (n-1) 個のエッジで構成されます。「n」は頂点 (またはノード) の数です。スパニング ツリーのエッジには重みが割り当てられている場合と、割り当てられていない場合があります。指定されたグラフ G から作成されるすべての可能なスパニング ツリーは同じ数の頂点を持ちますが、スパニング ツリー内のエッジの数は、指定されたグラフ内の頂点の数から 1 を引いたものと等しくなります。
完全な無向グラフには次のものがあります。 nn-2 スパニングツリーの数 n グラフ内の頂点の数です。仮に、 n = 5 の場合、可能なスパニング ツリーの最大数は次のようになります。 55-2= 125。
スパニングツリーの応用例
基本的に、スパニング ツリーは、グラフのすべてのノードを接続する最小パスを見つけるために使用されます。スパニング ツリーの一般的なアプリケーションのいくつかを次に示します。
- クラスター分析
- 土木ネットワーク計画
- コンピュータネットワークルーティングプロトコル
ここで、例を使用してスパニング ツリーを理解しましょう。
スパニングツリーの例
グラフが次のようになると仮定します -
上で説明したように、スパニング ツリーにはグラフと同じ数の頂点が含まれます。上のグラフの頂点の数は 5 です。したがって、スパニング ツリーには 5 つの頂点が含まれます。スパニング ツリーのエッジは、グラフの頂点の数から 1 を引いたものと等しくなります。つまり、スパニング ツリーには 4 つのエッジが存在します。
上のグラフから作成される可能性のあるスパニング ツリーの一部を以下に示します。
スパニングツリーのプロパティ
スパニング ツリーのプロパティの一部は次のとおりです。
- 接続されたグラフ G には複数のスパニング ツリーが存在する場合があります。
- スパニング ツリーにはサイクルやループがありません。
- スパニングツリーとは、 最小限の接続で、 したがって、ツリーから 1 つのエッジを削除すると、グラフが切り離されてしまいます。
- スパニングツリーとは、 最大限に非周期的、 したがって、ツリーにエッジを 1 つ追加するとループが作成されます。
- 最大値が存在する可能性があります nn-2 完全なグラフから作成できるスパニング ツリーの数。
- スパニングツリーには、 n-1 エッジ。「n」はノードの数です。
- グラフが完全なグラフの場合、最大 (e-n+1) 個のエッジを削除することによってスパニング ツリーを構築できます。ここで、「e」はエッジの数、「n」は頂点の数です。
したがって、スパニング ツリーは接続されたグラフ G のサブセットであり、切断されたグラフのスパニング ツリーは存在しません。
最小スパニングツリー
最小スパニング ツリーは、エッジの重みの合計が最小となるスパニング ツリーとして定義できます。スパニング ツリーの重みは、スパニング ツリーのエッジに与えられた重みの合計です。現実の世界では、この重みは距離、交通量、混雑、または任意のランダムな値と考えることができます。
最小スパニングツリーの例
例を使用して最小スパニング ツリーを理解しましょう。
上のグラフのエッジの合計は 16 です。 さて、上のグラフから作成される可能なスパニング ツリーのいくつかは次のとおりです。
したがって、指定された加重グラフに対して上記のスパニング ツリーから選択される最小のスパニング ツリーは次のようになります。
最小スパニングツリーの応用例
最小スパニングツリーの適用は次のようになります。
- 最小スパニング ツリーは、給水ネットワーク、通信ネットワーク、電力網の設計に使用できます。
- マップ内でパスを検索するために使用できます。
最小スパニングツリーのアルゴリズム
以下に示すアルゴリズムを使用して、重み付きグラフから最小スパニング ツリーを見つけることができます。
- プリムのアルゴリズム
- クラスカルのアルゴリズム
上記の両方のアルゴリズムについて簡単に説明します。
プリムのアルゴリズム - これは、空のスパニング ツリーから開始する貪欲なアルゴリズムです。グラフから最小スパニングツリーを見つけるために使用されます。このアルゴリズムは、エッジの重みの合計が最小化されるように、グラフのすべての頂点を含むエッジのサブセットを見つけます。
キャメルケースパイソン
プリムのアルゴリズムの詳細については、以下のリンクをクリックしてください。 https://www.javatpoint.com/prim-algorithm
クラスカルのアルゴリズム - このアルゴリズムは、接続された重み付きグラフの最小スパニング ツリーを見つけるためにも使用されます。クラスカルのアルゴリズムも、全体的な最適化に焦点を当てるのではなく、あらゆる段階で最適な解決策を見つける貪欲なアプローチに従っています。
プリムのアルゴリズムの詳細については、以下のリンクをクリックしてください。 https://www.javatpoint.com/kruskal-algorithm
それでは、この記事については以上です。この記事があなたにとって有益で有益であることを願っています。ここでは、スパニング ツリーとミニマム スパニング ツリーについて、そのプロパティ、例、アプリケーションとともに説明しました。