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

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

（永持 仁）