逆削除法
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2025/06/03 06:45 UTC 版)
逆削除法（ぎゃくさくじょほう、英: reverse-delete algorithm）とは、グラフ理論において辺重み付き連結グラフの最小全域木を求めるアルゴリズムの一種である。1956年、クラスカルによって初めて提案されているが、逆削除法と共に同じ論文内で提案されたクラスカル法とは異なったアルゴリズムである[1]。与えられたグラフが非連結の場合は、逆削除法によって各連結成分ごとに最小全域木を求めることができる。このように、非連結なグラフに対して逆削除法によって求まる連結成分ごとの最小全域木の集合は最小全域森（英: minimum spanning forest）と呼ばれる。
また、逆削除法は貪欲法の一種であり、アルゴリズムの各段階で最良の選択を踏む。同じく貪欲法に分類されるクラスカル法とは逆の選択を続けていく。クラスカル法では辺が空のグラフから逐次辺の追加を行うのに対し、逆削除法では元のグラフから逐次辺の削除を行うアルゴリズムである。逆削除法の手順は以下の通りである:
- 辺集合
これは与えられた元のグラフである。辺上に書かれている数値は辺の重みを表している。 
逆削除法ではまずグラフの中で重みが15で最も大きい辺の DE を選択する。仮に辺 DE を削除したとしてもグラフは連結性を保たれるため、辺 DE を削除する。 
残った辺の中で最も重みの大きな辺の FG を選択する。仮に辺 FG をグラフから削除したとしてもグラフの連結性は保たれるため、グラフから辺 FG を削除する。 
残った辺の中で最も重みの大きな辺の BD を選択する。仮に辺 BD をグラフから削除したとしてもグラフの連結性は保たれるため、グラフから辺 BD を削除する。 
残った辺の中で最も重みの大きな辺の EG を選択する。仮に辺 EG をグラフから削除するとグラフの連結性は失われるため、辺 EG を残して、次の重みの大きい辺 BC を選択する。辺 BC はグラフの連結性の判定によりグラフから削除される。 
残った辺の中で最も重みの大きな辺の EF を選択する。仮に辺 EF をグラフから削除したとしてもグラフの連結性は保たれるため、グラフから辺 EF を削除する。 
ここで、未探索の辺がなくなったため、アルゴリズムは終了し、残ったグラフが元のグラフの最小全域木である。
動作時間
逆削除法は頂点数
Optimization computes maxima and minima.
| 一般 | |
|---|---|
| 微分可能 |
| 凸最小化 | |||||||
|---|---|---|---|---|---|---|---|
| 線形 および 二次 |
|
| 系列範例 (Paradigms) |
|||||
|---|---|---|---|---|---|
| グラフ理論 |
|
||||
| ネットワークフロー |
|
- 逆削除法のページへのリンク
