二部グラフの最大マッチング・最小頂点被覆

Hopcroft-Karp法によって二部グラフの最大マッチングを求めます。

var a = initHopcroftKarp(n, m:int)

二部グラフの左側の頂点数を$n$, 右側の頂点数を$m$としたグラフを作ります。

頂点の追加

a.addEdge(u, v:int)

左の頂点$u$と右の頂点$v$を結ぶ辺を追加します。

a.maximum_maching():seq[(int, int)]

最大マッチングの一例を表すタプルの配列を返します

a.minimum_vertex_cover():(seq[int], seq[int])

最小頂点被覆、すなわち頂点集合$S$であってどの辺をとってもいずれかの端点が$S$に含まれるようなものの最小の頂点集合を返します。返り値の1つめの要素は最小頂点被覆に選ぶべき左の頂点集合、2つめの要素は右の頂点集合です。

a.minimum_stable_set():(seq[int], seq[int])

最小独立集合、すなわち頂点の集合であって任意の2つの頂点が辺で結ばれていない最小のものを返します。

a.minimum_edge_cover():seq[(int, int)]

最小辺被覆、すなわち辺の集合$S$であって、どの頂点をとっても$S$のいずれかの端点になっているようなものの最小のものを返します。