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

接続された無向グラフ$ 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年に発見されたプリムのアルゴリズムは、接続された重み付きグラフの最小スパンツリーを見つける欲張りアルゴリズムです。それは、すべての頂点を含むそのグラフのツリーを見つけ、ツリー内のすべてのエッジの合計の重みは、すべての可能な全域木以下です。プリムのアルゴリズムは、密グラフでより高速です。