アルゴリズム工学データベースグラフ

最大隣接順序を用いた最小カットアルゴリズム


Java を有効にするとデモが表示されます。
Please enable Java.

最大隣接順序 (maximum adjacency ordering) とは、 任意の節点を1番目の節点 v1 として選び、以下次のルールに従って、 全節点につけた v1 から vn までの順序[1]。 「1番目から i 番目までの節点 v1, ..., vi が選ばれた後、 番号の付いていない節点の中で、 v1, ..., vi の節点との間に最も多くの辺の重み持つ節点を選び、 (i+1) 番目の節点 vi+1 とする。」

デモにおいては、1番目の節点 v1 をマウスのクリックにより選び、 順に選ばれた節点が水色で表示され、 v1 から時計回りに配置されていきます。 最後の節点 vn に接続する辺を赤色で表示し、 その重み和 d(vn) と その辺集合による節点集合の分割(カット)を左側に記録します。 vn の次数 d(vn) は 最後の2節点 vn-1,vn を分離するカットの最小値に に等しいという性質[2]から、vn-1,vn を1節点に縮約します (これら2節点を分離するカットはもう調べる必要がないので)。 得られたグラフでは、節点を再び黄色で表示。 以上の操作を節点が1つになるまで繰り返してやります。 節点数-1個の記録されたカットのうち最小の値のものを選べば、 入力されたグラフの最小カットが得られます。

[1] H. Nagamochi and T. Ibaraki,
A linear-time algorithm for finding a sparse k-connected spanning subgraph of a k-connected graph, Algorithmica, vol. 7, 1992, pp. 583--596.

[2] H. Nagamochi and T. Ibaraki,
Computing the edge-connectivity of multigraphs and capacitated graphs, SIAM J. Discrete Mathematics, vol. 5, 1992, pp. 54--66.

永持 仁

土村 展之(tutimura@logopt.com)
<最終更新日 1999年10月1日 >