二部グラフのマッチング

2部グラフ

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

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

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

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

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

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

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

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

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

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

      GroupA    GroupB         (s),(t)は便宜的に追加する始点・終点
   ,----○--------○----,
  /      `--------,      \     ・GroupA→GroupB への辺は、マッチング可能な頂点間にのみ辺を張る。
(s)-----○--------○-----(t)   ・各辺の容量は 1 とする。
  \      ,--------'      /
   `----○--------○----'      ・(s)から(t)まで流せるだけ流すと、流量が最大マッチングに一致する。

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

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

増大路とは、以下のようなルートである。（増加路、増加道などともいう）

• 既にマッチング $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$ が、マッチングのいずれかの辺の端点となっている」ことを、「$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)$ のため、増大路を見つける手法は、単純ではあるがハマると遅い。

• Dinic 法とその時間計算量 - みさわめも

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

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

Python3

増大路探索の考え方を用いつつ高速化した方法。$O(\sqrt{V}E)$ で解ける。

ちゃんとは理解できていないが、ざっくり方針として以下のような感じ？

• 最初にBFSにより、最短経路DAGを構築する
• DAGの上で、深さが深くなる方向にのみDFSし、増大路を見つける
• DAGの構築により、何度も同じ箇所を探索しない、また増大路はなるべく短いのが見つかる

• Hopcroft-Karp Algorithm :: Tiramister's Blog

この発想は、より一般的に、最大流を求めるDinic法などに採用されているため、そちらを使うことにするのでいいかも。

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

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

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

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

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

ただし、ソートは必要。

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

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

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

• 社員が $N$ 人、仕事が $M$ 個ある
• 社員 $i$ さんが仕事 $j$ をすると、利益が $V_{i,j}$ 発生する。
• 社員と仕事は1対1対応
• 利益を最大化せよ。

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

最大重みマッチングは、最小費用流問題に帰着できる。合計を最小化したい場合はそのまま、最大化したい場合はコストを正負逆にして処理する。 以下、帰着した問題と目的（最大化/最小化）が違うと混乱するため、元の問題も最小重みマッチングだったことにする。

以下のようにグラフを作る。

      GroupA    GroupB         (s),(t)は便宜的に追加する始点・終点
   ,----○--------○----,
  /      `--------,      \     ・(s)→GroupA への辺は、容量1, コスト0
(s)-----○--------○-----(t)   ・GroupA→GroupB への辺は、マッチング可能な頂点間にのみ辺を張る。
  \      ,--------'      /       容量1, コストはその2つをマッチングさせるコスト
   `----○--------○----'      ・GroupB→(t) への辺は、容量1, コスト0

最小重みマッチングは流量に制約がないので、元々が非負のコストしか無い場合は「何も流さない」のが自明な最適になってしまう。 よって通常、問題として出る場合は辺コストは負である。（正のコストの辺はそもそも使う意味が無い）

辺コストに負が出てくる場合は、Dijkstraが使えないので解くのに不都合。
よって（他にもやりようはあるが、単純には）一律、一定値を加算して全て正にするとよい。
マッチング問題の場合、流量1ごとに、コストのある辺を通る回数は1回と決まっているので、結果から(一定値×流量)を減じると正しい答えとなる。 （一般的な最小費用流問題では、流量1あたりでコストのある辺を通る回数が定まらないため、他の方法を講じる必要がある）

ある程度まで進むと「これ以上マッチングするとコストが逆に増えてしまう」ケースも発生する。
（マッチング数を増やすには、コストの小さい1辺をやめて、コストの大きい2辺を使わないといけない場合）
フローで $S→T$ パスが1回見つかるたびに、そのパスを流すコスト（加算した一定値を引いて元に戻したもの）を確認し、負でなくなったらやめる、とすればよい。

ライブラリとして整備するには、問題によって加算する一定値（＝終了条件）が変わるので、ライブラリ自体に判定させるよりは、 最大まで流させ、1回流す毎の (累積流量, 累積コスト) のリストとして返すようなものがあると汎用性が高い。

• 参考
  • AtCoder Library MinCostFlow の min_cost_slope

流量（終了するまでのマッチング数）を $F$、頂点数を $N$、変数を $M$ として、$O(F(N+M)\log{(N+M)})$ で解ける。
一般的には $F \simeq O(N)$ となる。

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

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

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

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

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

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

• 社員が $N$ 人、仕事が $M$ 個ある
• 社員 $i$ さんが仕事 $j$ をすると、不満度が $C_{i,j}$ たまる
• 社員と仕事は1対1対応
• 全体でこなす仕事数を最大化するという条件のもと、社員の不満度の合計を最小化する

最大重みマッチング問題と同様、これも最小費用流に帰着できる。

この問題の場合は最大までマッチングさせるという条件が付いているので、辺コストにもともと正のものがあっても成立する。
（負のものも混じっているなら、最大重みマッチング問題と同様、一定値を加算しておけばよい）

最小費用流のグラフを構築し、最大まで流したときのコストが答えとなる。

頂点集合が $U,V$ に分けられる二部グラフで、 「全ての $U$ を $V$ にマッチングさせられるかどうか」を判定したい。

• ホールの定理
• Hallの結婚定理とその証明 | 高校数学の美しい物語

• 例題
  • 男性を $U$、女性を $V$ として、結ばれてもよいと互いに思っている両想いペア $(U_i,V_j)$ がいくつかある
  • 相手を上手く決めれば、全ての男性が希望の女性と結ばれることができるか？

ここで、以下の2つの一方が言えれば、もう一方が言えるという定理を、Hallの定理、結婚定理という。

1. 全ての $U$ を $V$ にマッチングさせられる
2. ある $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_{req}$ と $B$ 全てからなるグラフの最大マッチング数が $|A_{req}|$ ならよい
• ② $B_{req}$ をカバーするマッチングが存在する
  • $A$ 全てと $B_{req}$ からなるグラフの最大マッチング数が $|B_{req}|$ ならよい

これがともに成り立てばよい。

①の結果でマッチングされた辺の情報を残したまま、$A$ の任意頂点を戻した元のグラフを考える。
①の後なので、$A_{req}$ は全てマッチングされ、$B_{req}$ はされたりされてなかったりする。

マッチングされなかった $B_{req}$ の1つ $b_i$ から増大路を探すことを考える。
ただし、ここでの増大路探索は「$A$ 側の未マッチング頂点、または $B$ 側の任意頂点にたどり着いたら終わり」とする。
これを「準増大路探索」と呼ぶことにする。

$A$ 側の未マッチング頂点 $a_j$ にたどり着いたら、通常の増大路と同様、 使用辺を反転させればマッチング済み頂点をそのままに $b_i,a_j$ を加えたマッチングが作れる。

   A        B
   ● - - - ● bi    ●必須頂点
     `=====,         ○任意頂点
   ○ - - - ●       ===== 既存マッチング
     `=====,         - - - マッチングではないが辺はある
aj ○ - - - ●

$B$ 側の任意頂点 $b_j$ にたどり着いたら、$b_j$ からマッチングを奪える。（$b_i→b_j$ 間の辺を反転）
双方の必須頂点は外さずに $b_i$ を加えたマッチングが作れる。

   A        B           A        B
   ○ - - - ● bi       ○=======● bi
     `=====,       →     `- - -,
ak ● - - - ●          ●=======●
     `=====,              `- - -,
            ○ bj                ○

いずれも見つからない場合は？
それはあり得ないことを以下に示す。

②から「$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)$ ということになる。

ここで、$b_i$ 以外は全てマッチング済みなので、$|b_i 以外の U|=|\Gamma(U)|$、つまり $|U| \gt |\Gamma(U)|$ となってしまい、Hallの結婚定理に矛盾する。

よって、背理法により、準増大路探索で $A,B$ どちらかの探索対象の頂点は見つかることが保証される。

これを繰り返すと、①のマッチング結果から、双方のマッチング済み必須頂点を未マッチング状態に戻すこと無く、 ①ではマッチされなかった $B$ 側の必須頂点を全てマッチさせることができる。

条件を満たすマッチングが存在する判定さえできていれば、最大マッチングの数は、 （特に必須頂点・任意頂点の区別のない）通常の最大マッチングを求めればよい。

判定問題の証明と同様の議論で、ある最大マッチングの結果を元にマッチングされなかった各必須頂点から 準増大路を見つけ、任意頂点のマッチングを奪って自身のものとすることができるので、 「必須頂点が全てマッチされた、同数のマッチング」に変形できる。

通常のマッチングの後、実際に準増大路探索を実行すればよい。

また、より汎用的なアルゴリズムを使うなら、最小流量制約付き最大流に帰着してもよい。

• 最小流量制限付き最大流 - あなたは嘘つきですかと聞かれたら「YES」と答えるブログ