|
二部グラフ G=(U, V, E) を与えられたときに、その最大マッチングを列挙するプログラムを書いた
(nxbimatch @ bitbucket.org)。
力ずくで探索するのに欲しかったのだが、意外にそういうプログラムが見当たらなかったからだ。
二部グラフ最大マッチングを一つ取り出すアルゴリズムはよく知られていて、Hopcroft-Karp のアルゴリズムが \(O(n^{5/2})\) 時間で走る(\(n\) は頂点数)。
列挙するアルゴリズムは Uno の一つ当たり \(O(n)\) 時間のものが知られているが、計算量を落とすための工夫がややこしい。
工夫を落とすと計算量としては一つ当たり \(O(m)\) 時間しか保証できない(\(m\) は辺数)。
が、自分が考えたい二部グラフが次数制限付き、つまり辺数が頂点数の定数倍以内なので、実質的にこれで \(O(n)\) 時間が達成できる。
ということでこのわりと素朴なアルゴリズムを実装した。
アルゴリズムは以下のようになる。
GEN_MAXIMUM_MATCHING(G):
- G の最大マッチングを(Hopcroft-Karp で)一つ見つけ、M とする。
- G の辺に M は U から V, それ以外は V から U と向きを付けた有向グラフを D とする。
- GEN_MAXIMUM_MATCHING_ITER(D,M)
GEN_MAXIMUM_MATCHING_ITER(D,M):
- D に辺がなければ終了。
- D にサイクルがなければ、
GEN_MAXIMUM_MATCHING_ITER_PATH(D,M)
- サイクルの一つを C とし、C に沿って M の辺を交換したマッチングを M' とし、M' を出力する。
- C と M の共通辺の一つを e とする。
- D から e および e と端点を共有する全ての辺を取り除いたグラフを D+ とし、GEN_MAXIMUM_MATCHING_ITER(D+,M)
- D の辺を C に沿って反転し e を取り除いたグラフを D- とし、GEN_MAXIMUM_MATCHING_ITER(D-,M')
GEN_MAXIMUM_MATCHING_ITER_PATH(D,M):
- D に辺がなければ終了。
- D に長さ 2 の交替パスが存在しなければ終了。
- 長さ 2 の交替パスの一つを P とし、M に含まれる辺を e, 含まれない辺を f とする。
- M から e を取り除いて f を加えたものを M' とし、M' を出力する。
- D から f を取り除いたグラフを D- とし、GEN_MAXIMUM_MATCHING_ITER_PATH(D-,M)
- D から f および f と端点を共有する全ての辺を取り除いたグラフを D+ とし、GEN_MAXIMUM_MATCHING_ITER_PATH(D+,M')
素朴でない実装は、計算量を落とすために GEN_MAXIMUM_MATCHING_ITER の 3 でサイクルを"上手く"選択する。
アルゴリズムの中でいくつもの有向グラフを次々に作っているが、グラフの実装として採用した NetworkX ではコピーが非常に重たい操作なので、辺を抜いたり戻したりを繰り返す方が速い。
プログラムを読んで、一番直観的でない部分は多分ここ。
参考文献: |