離散数学-スパニングツリー

接続された無向グラフ$ G $の全域木は、$ G $のすべての頂点を最小限に含む木です。グラフには多くの全域木が含まれる場合があります。

最小スパニングツリー

重み付きの接続された無向グラフ$ G $のすべての可能なスパニングツリーの重み以下の重みが割り当てられたスパニングツリーは、最小スパニングツリー(MST)と呼ばれます。スパニングツリーの重みは、スパニングツリーの各エッジに割り当てられたすべての重みの合計です。

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

クラスカルのアルゴリズムは、接続された重み付きグラフの最小全域木を見つける欲張りアルゴリズムです。それは、すべての頂点を含むそのグラフのツリーを見つけ、ツリー内のすべてのエッジの合計の重みは、すべての可能な全域木以下です。

アルゴリズム

Step 1 −指定されたグラフ$ G(V、E)$のすべてのエッジを、エッジの重みに従って昇順に配置します。

Step 2 −グラフから最小の重み付きエッジを選択し、これまでに形成されたスパニングツリーとサイクルを形成するかどうかを確認します。

Step 3 −サイクルがない場合は、このエッジをスパニングツリーに含めます。それ以外の場合は破棄します。

Step 4 −スパニングツリーに$(V-1)$個のエッジが残るまで、手順2と手順3を繰り返します。

Problem

クラスカルのアルゴリズムを使用して、次のグラフGの最小全域木を見つけたいとします。

Solution

上記のグラフから、次の表を作成します-

エッジ番号 頂点ペア エッジの重み
E1 (a、b) 20
E2 (交流) 9
E3 (a、d) 13
E4 (b、c) 1
E5 (b、e) 4
E6 (b、f) 5
E7 (c、d) 2
E8 (d、e) 3
E9 (d、f) 14

次に、エッジの重みに関して昇順でテーブルを再配置します-

エッジ番号 頂点ペア エッジの重み
E4 (b、c) 1
E7 (c、d) 2
E8 (d、e) 3
E5 (b、e) 4
E6 (b、f) 5
E2 (交流) 9
E3 (a、d) 13
E9 (d、f) 14
E1 (a、b) 20

最後の図で5つのエッジすべてを取得したので、アルゴリズムを停止します。これは最小スパニングツリーであり、その合計の重みは$(1 + 2 + 3 + 5 + 9)= 20 $です。

プリムのアルゴリズム

数学者のVojtechJarnikとRobertC。Primによって1930年に発見されたプリムのアルゴリズムは、接続された重み付きグラフの最小スパンツリーを見つける欲張りアルゴリズムです。それは、すべての頂点を含むそのグラフのツリーを見つけ、ツリー内のすべてのエッジの合計の重みは、すべての可能な全域木以下です。プリムのアルゴリズムは、密グラフでより高速です。

アルゴリズム

  • グラフからランダムに選択された単一の頂点を使用して、最小全域木を初期化します。

  • すべての頂点がツリーに含まれるまで、手順3と4を繰り返します。

  • ツリーをまだツリーにない頂点に接続するエッジを選択します。これにより、エッジの重みが最小になり、エッジを含めてもサイクルが形成されません。

  • 選択したエッジと、それがツリーに接続する頂点を追加します。

Problem

プリムのアルゴリズムを使用して、次のグラフGの最小全域木を見つけたいとします。

Solution

ここでは、頂点 'a'から始めて、次に進みます。

これは最小全域木であり、その総重みは$(1 + 2 + 3 + 5 + 9)= 20 $です。