逆削除法

逆削除法（ぎゃくさくじょほう、英: reverse-delete algorithm）とは、グラフ理論において辺重み付き連結グラフの最小全域木を求めるアルゴリズムの一種である。1956年、クラスカルによって初めて提案されているが、逆削除法と共に同じ論文内で提案されたクラスカル法とは異なったアルゴリズムである^[1]。与えられたグラフが非連結の場合は、逆削除法によって各連結成分ごとに最小全域木を求めることができる。このように、非連結なグラフに対して逆削除法によって求まる連結成分ごとの最小全域木の集合は最小全域森（英: minimum spanning forest）と呼ばれる。

また、逆削除法は貪欲法の一種であり、アルゴリズムの各段階で最良の選択を踏む。同じく貪欲法に分類されるクラスカル法とは逆の選択を続けていく。クラスカル法では辺が空のグラフから逐次辺の追加を行うのに対し、逆削除法では元のグラフから逐次辺の削除を行うアルゴリズムである。逆削除法の手順は以下の通りである:

• 辺集合 ${\displaystyle E}$ を持つグラフ ${\displaystyle G}$ を与える。
• ${\displaystyle E}$ に含まれる辺を重みが大きいものから探索する。
• 各反復においてその辺を削除することでグラフの連結性が保たれるかを判定する。
• もしその辺を削除したときにグラフの連結性が保たれるならば、その辺を削除して次の辺の探索を行う。

手順

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

上記のグラフでの ${\displaystyle E}$ は辺集合であり、各辺には重みが与えられ、少なくとも頂点 ${\displaystyle v1}$、${\displaystyle v2}$ が含まれるような頂点の集合を含む。

例

以下の例では緑の辺がその反復において評価を行っている辺であり、赤の辺は削除されたことを表す。

	これは与えられた元のグラフである。辺上に書かれている数値は辺の重みを表している。
	逆削除法ではまずグラフの中で重みが15で最も大きい辺の DE を選択する。仮に辺 DE を削除したとしてもグラフは連結性を保たれるため、辺 DE を削除する。
	残った辺の中で最も重みの大きな辺の FG を選択する。仮に辺 FG をグラフから削除したとしてもグラフの連結性は保たれるため、グラフから辺 FG を削除する。
	残った辺の中で最も重みの大きな辺の BD を選択する。仮に辺 BD をグラフから削除したとしてもグラフの連結性は保たれるため、グラフから辺 BD を削除する。
	残った辺の中で最も重みの大きな辺の EG を選択する。仮に辺 EG をグラフから削除するとグラフの連結性は失われるため、辺 EG を残して、次の重みの大きい辺 BC を選択する。辺 BC はグラフの連結性の判定によりグラフから削除される。
	残った辺の中で最も重みの大きな辺の EF を選択する。仮に辺 EF をグラフから削除したとしてもグラフの連結性は保たれるため、グラフから辺 EF を削除する。
	ここで、未探索の辺がなくなったため、アルゴリズムは終了し、残ったグラフが元のグラフの最小全域木である。

動作時間

逆削除法は頂点数 ${\displaystyle V}$ と辺数 ${\displaystyle E}$に対して（ランダウの記号を用いて）時間計算量 ${\displaystyle O(E\log V(\log \log V)^{3})}$ で実行することができる。この計算量は以下のようにして達成される:

• 辺を重みの降順に並べ替える場合には時間計算量 ${\displaystyle O(E\log e)}$ で実行することができる。ここで、辺の総数は最大でも頂点数 ${\displaystyle V}$ に対して、${\displaystyle V^{2}}$ となることから、並べ替えは ${\displaystyle O(E\log V)}$ の時間計算量となる。
• 反復の回数は ${\displaystyle E}$ 回行われる。
• 一回の反復における辺の削除、グラフの連結性の判定、辺の再挿入については各動作時間計算量 ${\displaystyle O(\log V(\log \log V)^{3})}$ で実行することができる^[2]。

妥当性の証明

先にクラスカル法#正しさの証明に目を通すことで理解が容易になる。

妥当性の証明では二つの段階によって示される。始めにアルゴリズムの最後に求まる部分グラフが全域木であることを示し、続いてその全域木が最小全域木であることを示す。

全域木

各反復で生成された残りの部分グラフ ${\displaystyle g}$ は、（#手順節）7行目においてグラフの連結性の確認を行っているため、非連結にはならない。また、得られた部分グラフには閉路を含むことがない。なぜならば、仮に閉路が存在するとすると、閉路内に含まれる辺を探索する過程で最大重みの辺が削除されるからである。このことから、${\displaystyle g}$ は元のグラフの最小全域木でなければならない。

重みの最小性

次の命題 ${\displaystyle P}$ を帰納法によって示す：「もし ${\displaystyle F}$ をある while（反復）の終了時点で残っている辺を辺集合にもつグラフであるとすると、${\displaystyle F}$ の部分グラフであるような最小全域木が存在する」

1. 明らかに while（反復）の開始前では命題 ${\displaystyle P}$ が成り立つ。なぜならば、重み付き連結グラフでは必ず最小全域木が存在し、また、${\displaystyle F}$ の辺集合は元のグラフ全ての辺をもつ集合であるため、この最小全域木は必ず ${\displaystyle F}$ の部分グラフとなるからである。
2. 続いて、途中の反復におけるグラフ ${\displaystyle F}$ において命題 ${\displaystyle P}$ が成り立つと仮定し、${\displaystyle F}$ に含まれる最小全域木を ${\displaystyle T}$ とする。逆削除法のある反復において辺 ${\displaystyle e}$ を削除した後でも、（${\displaystyle T}$ とは異なる可能性のある）ある最小全域木 ${\displaystyle T'}$ が ${\displaystyle F}$ の部分グラフとして存在することを示す必要がある。
   1. もし今削除しようとする辺 ${\displaystyle e}$ が ${\displaystyle T}$ に含まれていないとすると、${\displaystyle T=T'}$ とすれば、${\displaystyle T}$ は ${\displaystyle F}$ の部分グラフであることから、命題 ${\displaystyle P}$ は成り立つ。
   2. そうでないとき、すなわち ${\displaystyle e}$ が ${\displaystyle T}$ に含まれている場合を考える。始めに、各反復では ${\displaystyle F}$ はグラフが非連結とならないような辺のみを削除するため、${\displaystyle e}$ の削除ではグラフの切断を引き起こされない。一方、${\displaystyle T}$ は木であることから、${\displaystyle e}$ を削除すると ${\displaystyle T}$ は非連結となる。つまり、${\displaystyle e}$ の削除によって ${\displaystyle T}$ を部分グラフ ${\displaystyle t1}$ と ${\displaystyle t2}$ に分割される。全体のグラフ（すなわち ${\displaystyle F}$）は ${\displaystyle e}$ の削除後も連結なので、${\displaystyle t1}$ と ${\displaystyle t2}$ を結ぶ他の経路が存在しなければならない。このことから、（削除前の）${\displaystyle F}$ には閉路 ${\displaystyle C}$ が存在する。この閉路の中には ${\displaystyle T}$ に含まれないが ${\displaystyle F}$ に含まれるような別の辺 ${\displaystyle f}$ が存在する必要がある（もし閉路のすべての辺が ${\displaystyle T}$ に属しているとすると、木の定義に違反する）。ここで、${\displaystyle T'=T-e+f}$ が ${\displaystyle F}$ の部分グラフである最小全域木であることを述べる。
   3. 始めに ${\displaystyle T'}$ が全域木であることを示す。木から辺を一本削除し、閉路を生じさせないような別の辺を追加すれば、同じ頂点集合を持つ別の木が得られる。${\displaystyle T}$ は全域木であったため、${\displaystyle T'}$ もまた全域木である。ここで注意しなければならないのは、辺 ${\displaystyle e}$ が削除されているため、辺 ${\displaystyle f}$ を追加したとしても閉路は生じない。
   4. 続いて、${\displaystyle T'}$ が最小全域木であることを示す。辺 ${\displaystyle e}$ および ${\displaystyle f}$ の重みについて3つの場合を考える（重み関数を ${\displaystyle wt}$ とする）
      1. ${\displaystyle wt(f)<wt(e)}$: このとき、${\displaystyle T'}$ の重みは ${\displaystyle T}$ よりも小さくなり、${\displaystyle T}$ が最小全域木であるという仮定に反する。
      2. ${\displaystyle wt(f)>wt(e)}$: このとき、重みの降順で辺を処理する際に、${\displaystyle f}$ は ${\displaystyle e}$ より先に評価されるべきである。さらに、閉路 ${\displaystyle C}$ が存在するため、${\displaystyle f}$ を削除しても ${\displaystyle F}$ が非連結にはならない。したがって、アルゴリズムは既に ${\displaystyle f}$ を削除しているはずであり、${\displaystyle F}$ に存在しないことになるが、これは矛盾する（手順4で ${\displaystyle f}$ の存在を示している）。
      3. よって、${\displaystyle wt(f)=wt(e)}$ でなければならない。このとき ${\displaystyle T'}$ も最小全域木であり、命題 ${\displaystyle P}$ は再び成り立つ。
3. 以上より、while （反復）が終了した時点（すべての辺が探索された時点）で命題 ${\displaystyle P}$ は成り立ち、${\displaystyle F}$ は全域木の辺集合であり、加えて、${\displaystyle F}$ は最小全域木の辺集合であることが示された。したがって、${\displaystyle F}$ が最小全域木の辺集合であることが導かれる。