目次
二部グラフのマッチング
前提
二部グラフとは
頂点集合をAとBの2つに分けたとき、全ての辺がAの1つとBの1つを結び、A同士・B同士を結ぶ辺がないような分け方ができるグラフ
以下の例でも出てくるが、「仕事と人員を最適に割り振る」「定員を超過しないようにできるだけ希望の部活に入部させる」など現実でも出てくる最適化問題を解く際、仕事をA、人員をBとしたグラフに見立てて考えることができ、グラフ理論の様々なセオリーを使える。
マッチングとは
グラフ上から、「どの2辺も両端の頂点を共有しない」という条件で選んだ辺集合を、マッチングと呼ぶ
- 極大マッチング
- もうこれ以上辺を追加で選べない状態
- 最大マッチング
- 極大マッチングのうち、辺の本数が最大のもの
- 完全マッチング
- 全頂点が、マッチングの辺のいずれかの端点になっているもの
- 必ず存在するとは限らない
- 必然的に最大マッチング
二部グラフでは効率的に解ける
最大マッチング
例
多対多の関係にある2つのものを、上手くマッチングさせることで最大化する時に用いる。
- 作業がN個ある
- 社員がM人いる
- 社員が1度に担当できる作業は1つまで。各作業は1人で担当すれば十分な量（要は1対1対応）
- 社員ごとに担当可能な作業（の候補）が決まっている
- どのように作業を社員に割り振すれば数を最大にできるか？
方針
こちらのブログが丁寧な図説でわかりやすい（Internet Archive）
最大流問題に帰結
グラフ理論に最大流問題というのがある。最大フロー問題
グラフを水道管のネットワークに見立てる。各リンクには最大で流せる容量が決まっている。 始点(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,...,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$ の最大マッチング
- 見つからなかったら、$M_{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になるだけ）
一度含まれていた頂点が、後のマッチング更新で含まれなくなることは無い。
逆に、含まれていない頂点 $a_k$ がマッチングに含まれるようになるには、$a_k$ を始点として増大路を発見する以外に無い。
よって、遡っての探索をしてマッチングが増える可能性があるとすれば、 「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)の組み合わせを、便宜的に“閉じたペア集団”と呼ぶことにする。
頂点 $a_k$ から増大路が見つからないというのは、頂点 $a_k$ から辺で繋がるBの頂点全てが、 すでに形成された閉じたペア集団のどれかに含まれてしまっているということ。
頂点 $a_{k+1},a_{k+2},...$ と進めていっても閉じたペア集団の部分が更新されることは無い。 よって、$a_k$ からの増大路が見つからないという状態は変化せず、遡っての探索を行う必要は無い。
計算量
頂点数を $V$、辺数を $E$ として、$O(VE)$
実際にはもっと早く終了することもあるが、探索順によって遅くなる。
a1 a2 a3 a4 a5 ... ｜／｜／｜／｜／｜ b1 b2 b3 b4 b5 ...
- a3→b3 を発見
- a4→b3→a3→b2 を発見
- a2→b2→a3→b3→a4→b4 を発見
- …
1回の探索で、それまでに決まったマッチング全てが再探索される可能性がある。
最大流を適切に実装したときは $O(\sqrt{V}E)$ のため、増大路を見つける手法は、単純ではあるがハマると遅い。
実装
二部グラフでは、元のグラフ情報の他には「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)))
Hopcroft-Karp のアルゴリズム
増大路探索の考え方を用いつつ高速化した方法。$O(\sqrt{V}E)$ で解ける。
ちゃんとは理解できていないが、ざっくり方針として以下のような感じ？
- 最初にBFSにより、最短経路DAGを構築する
- DAGの上で、深さが深くなる方向にのみDFSし、増大路を見つける
- DAGの構築により、何度も同じ箇所を探索しない、また増大路はなるべく短いのが見つかる
この発想は、より一般的に、最大流を求めるDinic法などに採用されているため、そちらを使うことにするのでいいかも。
最大重みマッチング
頂点や辺に何らかの価値が与えられて、それを最大化（最小化）する問題。
最大重みマッチング≠最大マッチング。（価値の高い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）
最小費用流問題に帰着できる。合計を最小化したい場合はそのまま、最大化したい場合は便宜上マイナスにして処理する。
ハンガリアン法
最大重みマッチングはハンガリアン法という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とする。
Hallの定理
頂点集合が $U,V$ に分けられる二部グラフで、 「全ての $U$ を $V$ にマッチングさせられるかどうか」を判定したい。
- 例題
- 男性を $U$、女性を $V$ として、結ばれてもよいと互いに思っている両想いペア $(U_i,V_j)$ がいくつかある
- 相手を上手く決めれば、全ての男性が希望の女性と結ばれることができるか？
ここで、以下の2つの一方が言えれば、もう一方が言えるという定理を、Hallの定理、結婚定理という。
- 全ての $U$ を $V$ にマッチングさせられる
- ある $U$ の部分集合を $S$ とする
- $S$ の少なくとも1つと結ばれている $V$ 側の頂点集合を $\Gamma(S)$ とする
- 全ての $S$ について、$|S| \le |\Gamma(S)|$ が成り立つ
つまり、男性を適当に選ぶと、その人数より、その人達と結ばれうる女性の人数の方が多い、ということが常に成り立てばよい。
1→2は直感的にわかる。男性より女性の方が少なければ必ず溢れる男性がいて、マッチング不成立となる。
2→1は、帰納法で証明できる。上記「高校数学の美しい物語」参照。
しかしそう言われても、一般的には $U$ の全ての部分集合を調べる方が最大マッチングより大変なので、「どう使うの？」となる。
「頂点数や辺数が膨大になって実際にグラフを作るのはとても無理だが、辺の張られ方に規則性がある場合」などで、上手く活用できる場面がある。
- $U_i$ からは、$V_{Li}～V_{Ri}$ の連続した区間に辺が張られるとか
- $U$ を更にその中でグループ化でき、同じグループからは同じ辺の張られ方をするとか
逆に言うと、競プロでは「Hallの定理だけで解ける」ような問題は出にくく、 より難しい考察の入口として使われることが多いかもしれない。
必ずマッチされなければならない頂点がある場合
頂点 $v_1,v_2,...$ が必ずマッチされていなければならないという条件下で、マッチングが存在するか？
また、最大マッチングはいくつか？
（説明上、そのような頂点を「必須頂点」、そうでない頂点を「任意頂点」と呼ぶことにする）
一方のグループのみに存在
頂点グループ $A$ と $B$ に分けたうちの $A$ のみに必須頂点 $\{a_1,a_2,...,a_k\}$ がある場合。
$A$ 側の各頂点から増大路の探索を行う際、必須頂点を優先的に探索する。
必須頂点 $a_1～a_{i-1}$ しかマッチングされていない状態で $a_i$ の増大路が見つからないなら、 条件を満たすマッチングは不可能である。 （$a_i$ をマッチングに組み入れるには、他の必須頂点を犠牲にするしかない）
逆に必須頂点が全てマッチングできたら（当然）可能で、その際の最大マッチングも求められる。
双方のグループに存在
グループ $A$ に必須頂点 $A_{req}=\{a_1,...,a_k\}$、$B$ に必須頂点 $B_{req}=\{b_1,...,b_l\}$ がある場合。
マッチング可否だけわかればよい
- ① $A_{req}$ をカバーするマッチングが存在する
- $a_1,...,a_k$ から順に増大路を探して全て見つかればよい
- ② $B_{req}$ をカバーするマッチングが存在する
- グラフをリセットし、$b_1,...,b_l$ から順に増大路を探して全て見つかればよい
これがともに成り立てばよい。
証明
①のマッチング結果は、$A$ 側の必須頂点は全てマッチングされ、$B$ 側はされたりされてなかったりする。
マッチングされなかった $B$ 側の必須頂点の1つ $b_i$ から増大路を探すことを考える。
ただし、ここでの増大路探索は「$A$ 側の未マッチング頂点、または $B$ 側の任意頂点にたどり着いたら終わり」とする。
$A$ 側の未マッチング頂点にたどり着いたら、通常の増大路と同様、 使用辺を反転させればマッチング済み頂点をそのままに $b_i$ を加えたマッチングが作れる。
A B ● - - - ● bi ●必須頂点 `=====, ○任意頂点 ● - - - ● ===== 既存マッチング `=====, - - - マッチングではないが辺はある ○ - - - ●
$B$ 側の任意頂点 $b_j$ にたどり着いたら、$b_j$ からマッチングを奪える。（$b_i→b_j$ 間の辺を反転）
双方の必須頂点は外さずに $b_i$ を加えたマッチングが作れる。
A B A B
○ - - - ● bi ○=======● bi
`=====, → `- - -,
ak ● - - - ● ●=======●
`=====, `- - -,
○ bj ○
いずれも見つからない場合は？
②から、「$B$ 側の必須頂点の全体集合 $B_{req}$ を全てカバーするマッチングが存在」することがわかっている。
よって、Hallの結婚定理により、$B_{req}$ の任意の部分集合 $U$ で、$|U| \le |\Gamma(U)|$ が成立する。
さて、今、$b_i$ から増大路を探索した結果、 $A$ 側の未マッチング頂点も $B$ 側の任意頂点も見つからなかったとする。
A B
●=======●
`- - -,
○=======●
`- - -,
● bi
,- - -'
●=======●
,- - -'
○=======●
,- - -'
●=======●
すると、ここで探索された $B$ 側頂点は当然、全て必須頂点であり、$B_{req}$ 側の任意の頂点集合の1つである。これを $U$ とする。
探索された $A$ 側頂点の集合が $\Gamma(U)$ ということになる。探索しきっているので、$U$ から接続される $A$ 側頂点はこれが全てである。
ここで、全てマッチング済みだったということは、$|U から b_i を除いた集合| = |\Gamma(U)|$ であり、 $|U| \gt |\Gamma(U)|$ となってしまい、Hallの結婚定理に矛盾する。
よって、背理法によりどちらかは見つかることが保証される。
これを繰り返すと、①のマッチング結果から、双方のマッチング済み必須頂点を未マッチング状態に戻すこと無く、 ①ではマッチされなかった $B$ 側の必須頂点を全てマッチさせることができる。
最大マッチングを求めたい
条件を満たすマッチングが存在する確認さえできていれば、最大マッチングの数は、 （特に必須頂点・任意頂点の区別のない）通常の最大マッチングを求めればよい。
判定問題の証明と同様の議論で、ある最大マッチングの結果を元に、マッチングされなかった各必須頂点から （任意頂点を含めた）増大路を見つけ、任意頂点のマッチングを奪って自身のものとすることができるので、 「必須頂点が全てマッチされた、同数のマッチング」に変形できる。
（数だけでなく、具体的なマッチングの一例が必要な場合は、この通り任意頂点を含めた増大路探索を実行すればよい）
また、より汎用的なアルゴリズムを使うなら、最小流量制約付き最大流に帰結してもよい。
