一般グラフの最大マッチング

マッチしていない頂点を根にして、マッチングの辺とそうでない辺が交互に並ぶ道(交互路)の木を BFS で広げます。根から偶数本の辺でたどり着ける頂点(外点)どうしが辺で結ばれると奇閉路(花)ができるので、その上の頂点をすべて外点にして 1 つの頂点のように扱い、探索を続けます。マッチしていない別の頂点に着いたら、根からそこまでの道(増加パス)の上でマッチングの辺とそうでない辺を入れ替えて、マッチングを 1 本増やします。花の扱いには Gabow の方法を使い、再帰は使いません。

最大マッチングの大きさは、返り値の長さです。二部グラフなら、二部マッチング(Hopcroft–Karp) のほうが速く動きます。

孤立点のないグラフでは、すべての頂点を覆うのに必要な辺の最小本数(最小辺被覆の大きさ)は、 $n$ から最大マッチングの大きさを引いた値です。

例(5 頂点の閉路の最大マッチングは 2 本):

print(general_matching(5, [(i, (i + 1) % 5) for i in range(5)]))  # [(0, 1), (2, 3)]

コード

def general_matching(n, edges):
    # 頂点 0..n-1、無向辺 edges = [(u, v), ...] のグラフの最大マッチング(Edmonds の花のアルゴリズムを Gabow の方法で)
    # マッチングの辺 (u, v)(u < v)のリストを u の昇順で返す。自己ループは無視し、多重辺はあってもよい
    # 中では頂点を 1..n とし、0 を番兵にする
    K = n + 1
    g = [[] for _ in range(K)]
    for u, v in edges:
        if u != v:
            g[u + 1].append(v + 1)
            g[v + 1].append(u + 1)
    mate = [0] * K  # mate[v] = v とマッチしている頂点(0 ならマッチしていない)
    for x in range(1, K):  # 最初に貪欲にマッチさせておく
        if mate[x] == 0:
            for y in g[x]:
                if mate[y] == 0:
                    mate[x] = y
                    mate[y] = x
                    break
    # label[v]: 負なら外点でない(-1 か、花を探すときの印)、0 は根、1..n は頂点ラベル、K 以上は辺ラベル
    # 外点 v の first[v] は、v から根への交互路で最初の外点でない頂点(外点を指していたら find でたどる)
    label = [-1] * K
    first = [0] * K

    def find(x):
        y = x
        while label[first[y]] >= 0:
            y = first[y]
        r = first[y]
        while label[first[x]] >= 0:  # 経路圧縮
            nx = first[x]
            first[x] = r
            x = nx
        return r

    for root in range(1, K):
        if mate[root]:
            continue
        label[root] = 0
        first[root] = 0
        q = [root]
        found = False
        for x in q:
            for y in g[x]:
                if mate[y] == 0 and y != root:
                    # 増加パスが見つかったので、根から x を通って y までの辺を付け替える
                    mate[y] = x
                    st = [x, y]
                    while st:
                        w = st.pop()
                        v = st.pop()
                        t = mate[v]
                        mate[v] = w
                        if mate[t] != v:
                            continue
                        lv = label[v]
                        if lv < K:  # 頂点ラベル
                            mate[t] = lv
                            st.append(lv)
                            st.append(t)
                        else:  # 辺ラベル (a, b): a 側を付け替えてから b 側を付け替える
                            a = lv // K - 1
                            b = lv % K
                            st.append(b)
                            st.append(a)
                            st.append(a)
                            st.append(b)
                    found = True
                    break
                if label[y] >= 0:
                    # x と y がともに外点で、奇閉路(花)ができた
                    r = find(x)
                    s = find(y)
                    if r == s:
                        continue
                    e = K * (x + 1) + y  # 辺ラベル
                    label[r] = label[s] = -e
                    # 2 つの交互路を交互にたどり、最初に合流する外点でない頂点 join を探す
                    while True:
                        if s:
                            r, s = s, r
                        r = find(label[mate[r]])
                        if label[r] == -e:
                            break
                        label[r] = -e
                    join = r
                    # join より手前の外点でない頂点に辺ラベルを付けて外点にする
                    for v in (first[x], first[y]):
                        while v != join:
                            q.append(v)
                            label[v] = e
                            first[v] = join
                            v = first[label[mate[v]]]
                else:
                    v = mate[y]
                    if label[v] < 0:
                        label[v] = x
                        first[v] = y
                        q.append(v)
            if found:
                break
        if found:
            for v in range(K):
                label[v] = -1
    return [(x - 1, mate[x] - 1) for x in range(1, K) if x < mate[x]]