二部グラフのマッチング

前提

二部グラフとは

頂点集合をAとBの2つに分けたとき、全ての辺がAの1つとBの1つを結び、A同士・B同士を結ぶ辺がないような分け方ができるグラフ

以下の例でも出てくるが、「仕事と人員を最適に割り振る」「定員を超過しないようにできるだけ希望の部活に入部させる」など現実でも出てくる最適化問題を解く際、仕事をA、人員をBとしたグラフに見立てて考えることができ、グラフ理論の様々なセオリーを使える。

マッチングとは

マッチング_(グラフ理論)

グラフ上から、「どの2辺も両端の頂点を共有しない」という条件で選んだ辺集合を、マッチングと呼ぶ

極大マッチング
- もうこれ以上辺を追加で選べない状態
最大マッチング
- 極大マッチングのうち、辺の本数が最大のもの
完全マッチング
- 全頂点が、マッチングの辺のいずれかの端点になっているもの
- 必ず存在するとは限らない
- 必然的に最大マッチング

二部グラフでは効率的に解ける

最大マッチング

例

多対多の関係にある2つのものを、上手くマッチングさせることで最大化する時に用いる。

作業がN個ある
社員がM人いる
社員が1度に担当できる作業は1つまで。各作業は1人で担当すれば十分な量（要は1対1対応）
社員ごとに担当可能な作業（の候補）が決まっている
どのように作業を社員に割り振すれば数を最大にできるか？

方針

こちらのブログが丁寧な図説でわかりやすい
PointyWizardHats - agwの日記 - TopCoder部

最大流問題に帰結

グラフ理論に最大流問題というのがある。最大フロー問題

グラフを水道管のネットワークに見立てる。各リンクには最大で流せる容量が決まっている。始点(source)と終点(sink)が与えられたとき、どのような経路をたどってもいいので、sourceからsinkまで合計で最大いくらの流量を流すことが可能か求める。二部グラフの左にsource、右にsinkを配置し、sourceとAの各頂点、sinkとBの各頂点をリンクで繋ぎ、各リンクの容量を1とすると、最大マッチングは最大流と一致する。

増大路を探す

もう一つの考え方として、増大路を見つからなくなるまで探す、というのがある。汎用性は無くなるが、二部マッチングを求めるだけならこちらの方が単純で高速。

増大路とは、以下のようなルートである。

既にマッチング $M$ がある
- マッチング: ペアとなる2頂点を結ぶ辺の集合
ペアのいない（$M$ のどの辺の端点にも含まれない）$A$ 側の点 $a_i$ を始点とする
「$M$ に含まれない辺」と「含まれる辺」を交互に辿る
ペアのいない（$M$ のどの辺の端点にも含まれない）$B$ 側の点 $b_k$ を終点とする

これが何だというと、この増大路の「含まれない辺」と「含まれる辺」を反転させると、辺の数が1本増えた新しいマッチングを作れる。

(※ "=="は既存のマッチング、"--"はマッチングではないが辺が存在する箇所)
ai--b1==a1--b2==a2-- ... --bx==ax--bk
↓
ai==b1--a1==b2--a2== ... ==bx--ax==bk
組み替えることで、マッチング数が1つ増えている

よって、以下の手順で最大マッチングを求めていく。

Aの頂点に、$a_1,a_2,\ldots,a_n$ と番号を付ける
頂点 $a_1–a_k$ と $B$ (とそれに付随する辺)から成るグラフを $G_k$ とする
いま、$G_{k-1}$ の最大マッチング $M_{k-1}$ が求まっているとして、$a_k$ を始点とした増大路を探す
増大路が見つかったら、含まれる辺と含まれない辺を反転させる
- その状態が $G_k$ の最大マッチング $M_k$ となる
- 頂点を1つ追加して増えるマッチング数は高々1つなので、$M_{k-1}$ が $G_{k-1}$ の最大マッチングなら、1本増えた $M_k$ は $G_k$ の最大マッチング
見つからなかったら、$G_{k-1} が変わらず $G_k$ の最大マッチング

Aの各頂点につき増大路を1回ずつ探索すれば良い。

$k=0$ のとき、$M_0=\phi$ が最大マッチングである。$k=1$ から始めて $n$ まで繰り返すと、帰納的に、全体の最大マッチング $M_n$ が求められる。

増大路は1つ見つかればどれでもよいので、深さ優先探索が使える。

Aは各1回の探索だけでいいの?

いい。

以下、「頂点aが、マッチングのいずれかの辺の端点となっている」ことを、「aがマッチングに含まれる」と表現する。

増大路でマッチングを更新しても、含まれる頂点は、始点と終点が増えるだけで他は変わらない。（s–b1==a1–tがs==b1–a1==tになるだけ）
一度含まれていた頂点が、後のマッチング更新で含まれなくなることは無い。

逆に、含まれていない頂点akがマッチングに含まれるようになるには、akを始点として増大路を発見する以外に無い。

よって、遡っての探索をしてマッチングが増える可能性があるとすれば、「1度目の探索で増大路の探索に失敗した頂点が、後で状態の変わったマッチングでは成功する」ことである。

そのようなことが起こりうるのか、考える。

増大路が見つからないときというのは、“閉じたペア集団”がいるということ。

A側の1,2,3が、いずれもB側のa,b,cとの間にしか辺が無い場合、組み合わせはどうあれ、全体として(1,2,3)-(a,b,c)間に3本のマッチング辺があるということは不変である。

もし(1,2,3)-(a,b,c)がマッチング済みの状態で、A側の4が、B側の[a,b,c]のいずれかから増大路を探そうとしても、

[a,b,c]→A に向かう移動は「マッチングに含まれる辺」を通るので、[1,2,3]のいずれかに行き着く
[1,2,3]→B に向かう移動は、それしか辺が無いので、[a,b,c]のいずれかに行き着く

を繰り返し、増大路の終点である「マッチングされていないBの頂点」には行き着かない。

このような(1,2,3)-(a,b,c)の組み合わせを、便宜的に“閉じたペア集団”と呼ぶことにする。

頂点akから増大路が見つからないというのは、頂点akから辺で繋がるBの頂点全てが、すでに形成された閉じたペア集団のどれかに含まれてしまっているということ。

頂点ak+1,2,3…と進めていっても閉じたペア集団の部分が更新されることは無い。よって、akからの増大路が見つからないという状態は変化せず、遡っての探索を行う必要は無い。

実装

二部グラフでは、元のグラフ情報の他には「B側の各頂点が、A側のどの頂点とマッチングしているか（あるいは未マッチか）」さえ覚えていれば良い。

再帰で深さ優先探索を行い、増大路発見でTrueを返す。発見時のみB側の頂点が指し示すマッチング相手のA側頂点の書き換えを行うと、すっきりしたコードで書ける。

Python3

Bipartite Matching | Aizu Online Judge

# XとYの二部グラフの最大マッチング X={0,1,2,...|X|-1} Y={0,1,2,...,|Y|-1}
#   edges[x]: xとつながるYの頂点のset
#   matched[y]: yとマッチングされたXの頂点(暫定)

def dfs(v, visited):
    """
    :param v: X側の未マッチングの頂点の1つ
    :param visited: 空のsetを渡す（外部からの呼び出し時）
    :return: 増大路が見つかればTrue
    """
    for u in edges[v]:
        if u in visited:
            continue
        visited.add(u)
        if matched[u] == -1 or dfs(matched[u], visited):
            matched[u] = v
            return True
    return False


# 標準入力からのグラフ読み取り
xn, yn, e = map(int, input().split())
edges = [set() for _ in range(xn)]
matched = [-1] * yn

for _ in range(e):
    x, y = map(int, input().split())
    edges[x].add(y)

# 増大路発見に成功したらTrue(=1)。合計することでマッチング数となる
print(sum(dfs(s, set()) for s in range(xn)))

最大重みマッチング

頂点や辺に何らかの価値が与えられて、それを最大化（最小化）する問題。

最大重みマッチング≠最大マッチング。（価値の高い1辺のために価値の低い2辺が犠牲になってもよい）

一方の頂点に重みがある例

宝箱が $N$ 個と鍵が $M$ 個ある
鍵は1つ宝箱を開けるとなくなる
鍵によって、開けられる宝箱の候補が決まっている
宝箱 $b_1$ ～ $b_n$ には、それぞれ $v_1$ ～ $v_n$ の価値のお宝が入っている
上手く開けて、より多くのお宝をGETだぜ

これは、宝箱側をA、鍵側をBとして、Aから負の価値を持つものは除いた後、価値の高い順にソートし、最大マッチングをおこなえば良い。マッチングに含まれる宝箱の価値の合計が答え。

宝箱は開ければ開けるほど得なので、開けられる限り貪欲に開けていく最大マッチングで良い。

ただし、ソートは必要。

増大路が見つからない場合でも、途中までの探索経路に含まれる宝箱を1つ犠牲にすれば開けられる。探索経路に含まれるということは過去にマッチング成功済みなので開けられることはわかっているが、もし現在検証中の宝箱より価値が低ければ、組み替えた方が良いことになる。

ソートし、過去に開けた宝箱の価値が現在検証中のものより必ず高いか同じ状態にしておくことで、そのような遡っての組み替えが必要ないことが保証できる。

辺に重みがある例

一般的に、「最大重みマッチング」というとこっち。「割り当て問題」とも言う。

宝箱が $N$ 個と鍵が $M$ 個ある
鍵は1つ宝箱を開けるとなくなる
鍵によって、開けられる宝箱の候補が決まっている
鍵 $a_i$ で宝箱 $b_j$ を開けると、価値 $v_{ij}$ の財宝が出てくる
上手く開けて、より多くのお宝をGETだぜ

H29年度 | 数理経済学 - TOKYO TECH OCW（第4回p.17～20）

最小費用流問題に帰着できる。合計を最小化したい場合はそのまま、最大化したい場合は便宜上マイナスにして処理する。

ハンガリアン法

yasuabe blog: 手作業でハンガリー法 Hangarian Algorithm

最大重みマッチングはハンガリアン法という2次元の行列ベースで解くアルゴリズムがある。$O(N^3)$

行と列ごとに、最小値を探して引いていく。小サイズなら手作業でも解くことが可能となる。

ハンガリアン法の場合、以下の2つが要求されるが、

行と列（頂点集合$A$と$B$のサイズ）は等しい
完全二部グラフであり、完全マッチングを求める

完全グラフでなくても、辺が無い部分にはコスト0の辺を仮定すれば解ける。また、行列サイズが異なっても小さい方にダミーで全てコスト0の列（行）を追加して調整して問題ない。

最小重み最大マッチング

例

農家がN件と、育てる作物がMつある
農家aiさんが作物bjを作るには、コストcijかかる
収穫量はどの農家が作っても同じとする
できるだけ沢山の作物を作りつつ、全体のコストを最小化する

最小費用流問題に帰結

グラフの辺に「この路を流せる最大容量」「この路を1単位流すのに必要なコスト」が設定されているとき、sourceからsinkまでFの容量を流すのに最低限必要な総コストを求める問題を、最小費用流問題という。

最大マッチングと同様、Aの左にsourceを置いてAの各点と結び、Bの右にsinkを置いてBの各点と結び、全辺の容量を1とする。

コストはA-B間はそのまま、source-A間やB-sink間は0とする。