逆削除法

逆削除法について

逆削除法（ぎゃくさくじょほう、英: reverse-delete algorithm）は、グラフ理論における特定のアルゴリズムです。この手法は、辺に重みが付けられた連結グラフにおける最小全域木を見つけるために使用されます。1956年にジャ セフ・クラスカルによって初めて提唱され、その後多くの場面で利用されています。特徴的な点は、このアルゴリズムがクラスカル法とは異なり、辺の削除を通じて最適な結果を得る点です。

逆削除法の基礎

逆削除法は、与えられたグラフが非連結である場合でも、各連結成分に対してそれぞれの最小全域木を求めることができます。このようにして得られる、非連結なグラフに対する最小全域木の集合は、最小全域森（英: minimum spanning forest）と呼ばれます。

アルゴリズムの流れ

逆削除法は貪欲法の一種であり、手順は次のように進行します。

1. 与えられた辺の集合 E を持つグラフ G の辺を、重みが大きい順にソートします。
2. 各辺について、その辺を削除してもグラフの連結性が保たれるかをチェックします。
3. もしその辺を削除した結果、グラフが連結であれば、その辺を取り除き、次の辺を評価します。

以下が具体的な手順の疑似コードです:
```plaintext
function ReverseDelete(edges[] E) is
sort E in decreasing order
Define an index i ← 0

while i < size(E) do
Define edge ← E[i]
delete E[i]
if graph is not connected then
E[i] ← edge
i ← i + 1

return edges[] E
```

動作時間

逆削除法の計算時間は、頂点数を V、辺数を E とした場合、次のように表されます。
O(E log V (log log V)³)
この計算量は、具体的には以下の点に依存しています:

• - 辺の重みの降順にソートする際の計算量は O(E log V) です。
• - 各反復における辺の削除や連結性のチェックは O(log V (log log V)³) の計算量が必要です。これにより、全体の計算量が導かれます。

妥当性の証明

逆削除法が正しい理由については、二つの主なステップがあります。最初に、このアルゴリズムによって生成された部分グラフが全域木であることが示され、次に、それが最小全域木であることを証明します。試みに、このアルゴリズムの反復プロセスで生成される部分グラフは、その時点での最大重みの辺が削除されるため、閉路を持たないという特徴があります。

最小性の確認

最小全域木が常に存在し、また、逆削除法で生成されるものがその特徴を満たしていることが分かります。また、もし連結である辺を削除しても、他の経路が存在するため、木の性質が保たれます。このことから、得られるすべての部分グラフが元のグラフの最小全域木でなければならないと考えられます。

結論

逆削除法は、効率的に辺重み付きグラフの最小全域木を見つけるアルゴリズムとして、様々な応用が可能です。特に、グラフが非連結である場合でも連結成分ごとの最小全域森を取得できる点が、このアルゴリズムの魅力であり、グラフの性質を理解する上でも重要です。

もう一度検索