Chu-Liu/Edmonds のアルゴリズム - 情報科学と人工知能のノート

有向最小全域木問題を解くアルゴリズム．1965 年に Chu と Liu が提案し、それとは独立に Edmonds が 1967 年に提案したらしいです．

定義

入力：グラフ $G=(V,E)$ 、コスト関数 $c:E\rightarrow\mathbb{Q}_{\geq 0}$ 、根 $r \in V$ ．
解： $r$ を根とした有向全域木．すなわち $r$ から全ての頂点への経路が存在する有向木 $T=(V,E')$ ．
解のコスト：有向全域木に含まれる各辺のコストの和．
出力：コスト最小の解．

直観的な説明

まず、 $G$ 上の根以外の全ての頂点 $v$ に対して、 $v$ に入る辺の中でコストが一番小さいものを選びます．選んだ辺だけからなるグラフが $r$ を根とする有向木になっていたら、明らかにこの木が与えられた問題の解です．一方、入ってくる辺の無い頂点があれば、与えられた問題は解を一つも持ちません．

選んだ辺だけからなる $G$ の部分グラフ $H$ が木になっていない場合、 $H$ は有向閉路を含んでいます．なぜならば、頂点に対して一つずつしか辺を選んでいないので DAG が発生することはありえません．また頂点に対して必ず一つ辺を選んでいるので閉路を含まずに分裂すること、すなわち有向森になることもありえません．DAG を含んでいるわけでもなく、木でも森でもないので、 $H$ のどこかには一つ以上の有向閉路が存在します．

$H$ に含まれていない辺を使って全域木を作るとコストが大きくなるため、なるべく $H$ 中の辺を多く使いたいのですが、 $H$ 中の全ての辺を使うとサイクルができてしまいます．Chu-Liu/Edmonds のアルゴリズムでは、 $H$ のそれぞれのサイクルについて、サイクル上の辺を一本だけ取り除き、代わりにサイクル外の辺を一つだけ使って全域木を作ることを試みます．なお明らかに、いずれかのサイクルについて二本以上のサイクル外の辺が使われて作られている有向全域木は、それぞれのサイクルについてサイクル外の辺を一本だけ使って作った有向全域木よりもコストが大きくなります．

具体的には、Chu-Liu/Edmonds のアルゴリズムでは $H$ のサイクルを利用して $G$ から新たなグラフ $G'$ を作り、そのグラフ上で有向最小全域木問題を再帰的に解きます． $G'$ は次の処理を $H$ からサイクルが無くなるまで繰り返すことによって作られます．

$H$ 上からサイクルを一つ取り除く．サイクルに含まれていた頂点を $v_1, \cdots, v_k$ とおく．
からを取り除き、新たな頂点を加える．
1. $v_i \in \{v_1, \cdots, v_k\}$ からサイクル上の他の頂点へ向かう辺は取り除く．
2. $v_i \in \{v_1, \cdots, v_k\}$ から外に出ていく辺 $(v_i, v'')$ はコストをそのままに $(v', v'')$ に置き換える．
3. サイクル外の頂点 $v''$ から $v_i \in \{v_1, \cdots, v_k\}$ に入る辺 $(v'', v_i)$ は $(v'', v')$ に置き換える．ただし $(v'', v')$ のコストは $c(\{v'', v_i\}) - c(\{v_{i-1}, v_i\})$ とする．
根が縮約された場合にはその縮約頂点を新たな根とする．

で、 $G'$ 上で最初の方法と同様にそれぞれの頂点に対してコストの小さい辺を選び、 $G'$ 上の最小有向全域木が見つからない場合には更に再帰的に処理を繰り返します．

再帰のある段階で最小有向全域木 $T'$ が発見されたら、 $T'$ 上で縮約した頂点を元に戻すことによって一つ前の段階のグラフの最小有向全域木を構築します．具体的には、 $T'$ 上の縮約した頂点 $v'$ に対し、縮約前のサイクル上の頂点が $v_1, \cdots, v_k$ で、 $T'$ 上で $v'$ に入る辺 $(v'', v')$ が元は $(v'', v_i)$ （ただし $v_i \in \{v_1, \cdots, v_k\}$ ）を置き換えた辺だったとすると、 $T'$ には $(v_{i-1}, v_i)$ 以外のサイクル上の辺と $(v'', v_i)$ を加えます．

$T'$ を出力した段に対する入力グラフを $G'$ とおくと、辺 $(v_{i-1}, v_i)$ のコストを $(v'', v_i)$ のコストから予め引いておいたため、 $G'$ の任意の全域木 $T''$ について、 $T''$ のコストに縮約したそれぞれのサイクル上の辺のコストを足した値は、 $T''$ の縮約頂点を上記のようにして展開して作った有向全域木のコストと等しくなります．すなわち $T'$ の最小性が縮約頂点を展開して作った有向全域木にも引き継がれるため、Chu-Liu/Edmonds のアルゴリズムは正しく最小有向全域木を返すことが保証されます．

擬似コード

上記の説明そのままですが、このアルゴリズムの擬似コードは以下のようになります．計算量求めやすくするために書いただけなので詳細は省略．実装するときには細かいところがかなり長くなるはずです．

${\rm Chi-Liu/Edmonds}(G = (V, E), r)$
　　// 小さなコストの辺を求める．
　　 $M[v] \leftarrow {\rm Null}, \forall v \in V$ ;
　　 ${\rm for}\ e = (u,v) \in E$
　　　　 ${\rm if} M[v] = {\rm Null or} \ c(M[v]) > c(e)\ {\rm then}$
　　　　　　 $M[v] \leftarrow e$ ;
　
　　// サイクルを探しつつグラフを縮約する．
　　 $G' = (V', E') \leftarrow G$ ;
　　 $r' \leftarrow r$ ;
　　 $#comp \leftarrow 0$ ;
　　 ${\rm for} \ (V, M)$ 上のサイクル $C$
　　　　 $G'$ から $C$ 上の頂点と辺を取り除く;
　　　　 $G$ で $C$ に出入りしている辺を $G'$ で加工する;
　　　　 $#comp++$ ;
　
　　 ${\rm if} \ #comp = 0 \ {\rm then}$
　　　　 ${\rm return} \ M$ ;
　　 ${\rm else}$
　　　　 $T \leftarrow {\rm Chu-Liu/Edmonds}(G', r')$ ;
　　　　 ${\rm for} \ (V, M)$ 上のサイクル $C$
　　　　　　 $T \leftarrow$ $T$ 上で $C$ の縮約頂点を元に戻し不要な辺を一本除いたもの;
　　　　　　 ${\rm return} \ T$ ;

計算量

一番最初の有向グラフ $G = (V, E)$ について $n = |V|, m = |E|$ とおきます．

まず、 $M$ がサイクルを含む場合、サイクルの縮約によって頂点の個数が少なくとも一つ減ります．よって再帰の段数は高々 $n$ 回です．

再帰の各段について、 $M$ を求める処理は、明らかに高々 $O(m)$ ステップです．全てのサイクルを求める処理は $O(n)$ で行うことができます．また、得られたサイクルを用いて $G'$ を作る処理は、 $G$ 上の頂点と辺を高々一回消し、それと高々同程度の数の頂点と辺を付け加えるだけですから $O(n + m)$ ステップで行うことができます．再帰によって得られた全域木上の縮約頂点を元に戻す作業も同様です．
よって全体の実行ステップ数は $O(n \times m)$ となります．

一方、使用メモリについても、再帰の各段でグラフや全域木を構築するために $O(n + m)$ ワード必要になりますから、全体で $O(n \times m)$ ワード必要になります．