3-2 増加路
一人分を増やすには既存の割当を動かす
現在のmatchingに未割当の学生 $a$ がいるとします。$a$ が希望する研究室1は学生 $b$ に割当済みでも、$b$ を空いている研究室2へ移せるなら
$$
a-1-b-2
$$
という交互の鎖に沿って割当を反転できます。辺 $a1,b2$ を採用し、辺 $1b$ を外せば、matchingの辺数が一つ増えます。
この局所的な組替えが、「これ以上増やせない」ことを判定する完全な基準になります。maximum matchingであることとaugmenting pathが存在しないことが同値だというBergeの補題を証明します。
maximalとmaximumを区別する
matching $M$ が極大マッチング|maximalであるとは、$M$ に新しい辺を一本加えてより大きなmatchingにできないことをいう。
matching $M$ が最大マッチング|maximumであるとは、$G$ の任意のmatching $N$ に対して
$$
|M|\ge|N|
$$
となることをいう。maximum matchingの辺数をマッチング数|matching numberといい $\nu(G)$ と書く。
maximumならmaximalですが、逆は偽です。四頂点path $1-2-3-4$ で $M=\{23\}$ は、端点を共有しない辺を追加できないのでmaximalです。しかし $\{12,34\}$ は二辺のmatchingなので、$M$ はmaximumではありません。
alternating pathとaugmenting path
matching $M$ に対し、matchingに属さない辺と属する辺が交互に現れるpathを $M$-交互路|alternating pathという。
両端が $M$ に飽和されておらず、最初と最後の辺が $M$ に属さない $M$-alternating pathを $M$-増加路|augmenting pathという。
augmenting pathの辺数は奇数で、非matching辺がmatching辺より一つ多くなります。二集合 $A,B$ のsymmetric differenceを
$$
A\triangle B=(A\setminus B)\cup(B\setminus A)
$$
と書きます。$M\triangle E(P)$ は、path上のmatching辺を外し、非matching辺を入れる操作です。
$P$ が $M$-augmenting pathなら
$$
M'=M\triangle E(P)
$$
はmatchingであり、$|M'|=|M|+1$ である。
$P$ の内部頂点では、path上の二辺の一方が $M$ に属し、他方が属しません。反転後もその二辺のうち一方だけが選ばれます。pathの両端は元の $M$ で未飽和であり、反転後は最初または最後の非matching辺一本だけに接続します。
path外では $M$ を変えません。path内部の頂点がpath外の $M$-辺にも接続することはありません。もしあれば、内部頂点はpath上の $M$-辺と合わせて二本のmatching辺に接続するからです。従って $M'$ はmatchingです。
$P$ 上では非matching辺がmatching辺より一本多いので、反転により辺数は1増えます。□
二つのmatchingの差はpathと偶cycleに分かれる
二つのmatching $M,N$ に対し、辺集合 $M\triangle N$ が誘導する部分グラフの各非孤立連結成分は、次のいずれかである。
- $M$ と $N$ の辺が交互に並ぶpath。
- $M$ と $N$ の辺が交互に並ぶ偶数長cycle。
特に各成分で、$M$-辺数と $N$-辺数の差の絶対値は高々1である。
各頂点には $M$ の辺が高々一本、$N$ の辺が高々一本接続します。従って $M\triangle N$ 内の次数は高々2です。有限連結グラフで全頂点次数が高々2なら、非孤立成分はpathまたはcycleです。
同じmatchingの二辺は端点を共有しないため、成分内で隣り合う二辺がともに $M$、またはともに $N$ に属することはありません。従って辺は交互に並びます。cycleでは交互に出発種類へ戻るため長さは偶数で、両matchingの辺数は等しいです。pathでは両端の辺種類が同じならその種類が一本多く、異なれば同数です。□
Bergeの補題
有限グラフ $G$ のmatching $M$ がmaximumであるための必要十分条件は、$M$-augmenting pathが存在しないことである。
$M$-augmenting pathがあれば、反転補題により辺数が $|M|+1$ のmatchingを作れるので、$M$ はmaximumではありません。
逆に $M$ がmaximumでないとします。$|N|>|M|$ を満たすmatching $N$ を取ります。$M\triangle N$ を前補題によりpathと偶cycleへ分解します。
全成分を合わせると $N$-辺が $M$-辺より多いので、少なくとも一成分では $N$-辺が $M$-辺より多くなります。cycleでは同数で、pathで差は高々1なので、その成分は最初と最後がともに $N$-辺であるalternating pathです。
このpathの両端には $M$-辺が接続しません。もしpath外に $M$-辺があれば、その辺は $N$ に属さないため $M\triangle N$ に入り、同じ成分のpathをさらに延長するからです。従って両端は $M$ で未飽和で、このpathは $M$-augmenting pathです。
よってaugmenting pathがなければ $M$ はmaximumです。□
この定理は任意の有限グラフで成り立ちます。ただしaugmenting pathを効率よく見つける方法は、二部グラフと一般グラフで異なります。二部グラフでは単純な交互探索で十分ですが、一般グラフではodd cycleを縮約するblossomの処理が必要です。
二部グラフで交互探索をする
二部グラフ $G=(X\sqcup Y,E)$ とmatching $M$ を考え、未飽和な $X$ 頂点を全て探索の根にします。
- 全ての未飽和頂点 $x\in X$ をqueueへ入れ、rootとして印を付ける。
- $X$ 頂点からは $M$ に属さない辺だけを $Y$ 側へたどる。
- 到達した $Y$ 頂点が未飽和なら、親pointerを逆にたどってaugmenting pathを返す。
- 到達した $Y$ 頂点がmatching辺 $yx'$ をもつなら、その一本だけをたどって $x'$ を探索へ加える。
- queueが空になるまで3が起こらなければ、augmenting pathなしと報告する。
算法 [32-alg-bipartite-augmenting-search] が未飽和 $Y$ 頂点へ到達したとき、親pointer pathは $M$-augmenting pathである。到達せず終了したなら、$M$-augmenting pathは存在しない。
未飽和 $X$ rootから未飽和 $Y$ へ至る親pointer pathは、構成上、非matching辺から始まり、matching辺と非matching辺を交互に通り、非matching辺で終わります。探索木内のpathなので頂点を繰り返しません。両端が未飽和なのでaugmenting pathです。
逆に $M$-augmenting path
$$
x_0,y_1,x_1,y_2,\ldots,x_{k-1},y_k
$$
が存在するとします。$x_0$ は未飽和なので最初からqueueに入ります。$x_{i-1}$ が到達済みなら、非matching辺 $x_{i-1}y_i$ を算法は調べるので $y_i$ へ到達します。$i< k$ なら $y_i$ のmatching辺はpath上の $y_ix_i$ ただ一つなので、算法は $x_i$ へ進みます。帰納法により未飽和終点 $y_k$ へ到達し、成功するはずです。従って失敗終了時にaugmenting pathは存在しません。□
空matching $M=\varnothing$ から始める。前算法で $M$-augmenting path $P$ が見つかる限り
$$
M\leftarrow M\triangle E(P)
$$
と更新する。pathが見つからなければ $M$ を出力する。
反復算法は有限回で停止し、二部グラフのmaximum matchingを出力する。孤立頂点を前処理し、隣接listによるBFSを毎回最初から行えば、計算時間は
$$
O(|V||E|)
$$
である。
一回の反転ごとにmatchingの辺数は1増えます。matching辺数は高々 $\min(|X|,|Y|)\le |V|/2$ なので有限回で停止します。停止時には探索定理によりaugmenting pathがなく、Bergeの補題からmaximumです。
一回のBFSでは各頂点を高々一度queueへ入れ、各辺を高々定数回調べるため $O(|V|+|E|)$ 時間です。孤立頂点を除いたグラフでは全頂点に接続辺があり、次数和から $|V|\le2|E|$ です。反復回数は $O(|V|)$ なので全体は $O(|V||E|)$ です。□
高速なHopcroft--Karp算法は、最短augmenting pathを一度に複数反転して $O(\sqrt{|V|}|E|)$ を達成します。本章のCoreは単純算法までとし、速度改善はFurther Topicsに置きます。
失敗した探索はHall障害を返す
左側 $X$ の全頂点を飽和したいのに探索が失敗したとします。探索で到達した頂点を左右に分けて $Z_X\subseteq X,Z_Y\subseteq Y$ と書きます。
二部グラフで $M$ がmaximumだが $X$ を飽和しないとする。全ての未飽和 $X$ 頂点から交互探索を行い、到達集合を $Z_X,Z_Y$ とする。このとき
$$
N(Z_X)=Z_Y,\qquad |Z_X|>|Z_Y|.
$$
従って $Z_X$ はHall条件の失敗を具体的に証明する。
$x\in Z_X$ の任意の隣接頂点 $y$ を考えます。辺 $xy$ が $M$ に属さなければ探索規則により $y\in Z_Y$ です。$xy\in M$ なら、$x$ は未飽和rootではなく、$x$ へ到達するときにそのmatching辺を $y$ からたどっています。従ってやはり $y\in Z_Y$ です。ゆえに $N(Z_X)\subseteq Z_Y$。逆に $Z_Y$ の頂点は $Z_X$ からの辺で到達したので $Z_Y\subseteq N(Z_X)$ です。
$M$ はmaximumなのでaugmenting pathがなく、到達した $Y$ 頂点は全て $M$ で飽和されています。各 $y\in Z_Y$ のmatching相手は探索規則により $Z_X$ に入ります。反対に、$Z_X$ のうちrootでない頂点は、到達した $Y$ 頂点のmatching相手として入ります。
従って $M$ は $Z_Y$ と「$Z_X$ から未飽和rootを除いた部分」の間に全単射を与えます。未飽和rootは少なくとも一つあるので
$$
|Z_X|>|Z_Y|=|N(Z_X)|.
$$
□
成功時にはより大きいmatching、失敗時には不可能性を示す集合が得られます。算法が答えだけでなく証明書も返す典型例です。
具体例――三人の割当を組み替える
$$
X=\{a,b,c\},\qquad Y=\{1,2,3\}
$$
とし
$$
N(a)=\{1\},\quad N(b)=\{1,2\},\quad N(c)=\{2,3\}.
$$
現在のmatchingを $M=\{b1,c2\}$ とします。$a$ は未飽和です。交互探索は
$$
a\xrightarrow{\notin M}1
\xrightarrow{\in M}b
\xrightarrow{\notin M}2
\xrightarrow{\in M}c
\xrightarrow{\notin M}3
$$
というaugmenting pathを見つけます。反転すると
$$
M'=\{a1,b2,c3\}
$$
となり、三人全員が割り当てられます。
一般グラフで何が難しくなるか
三角形のようなodd cycleでは、根からある頂点へ偶数長で到達したか奇数長で到達したかが、左右の部で固定されません。交互探索木の二枝を結ぶ辺が現れたとき、二部グラフのように直ちにaugmenting pathとも失敗とも判定できない場合があります。
Bergeの補題自体は一般グラフでも正しいので、課題は探索です。Edmondsのblossom算法は交互なodd cycleを一頂点へ縮約し、縮約グラフで見つけたpathを元へ展開します。この処理はFurther Topicsとし、Coreでは二部グラフ算法を完全に扱います。
演習
六頂点path $1-2-3-4-5-6$ で、maximalだがmaximumでないmatchingを一つ挙げ、そのmatchingに対するaugmenting pathを示せ。
$M=\{23,45\}$ とします。未使用辺12は頂点2、34は既存二辺の端点、56は頂点5と接するため、どの辺も追加できずmaximalです。
しかしpath $1,2,3,4,5,6$ は
$$
12\notin M, 23\in M, 34\notin M, 45\in M, 56\notin M
$$
と交互で、両端1,6は未飽和です。反転すると $\{12,34,56\}$ となり、辺数3のperfect matchingを得ます。□
cycle $C_6$ の辺を順に $12,23,34,45,56,61$ とし
$$
M=\{12,34,56\},\qquad N=\{23,45,61\}
$$
とする。$M\triangle N$ の成分と辺の交互性を調べよ。
$M,N$ は共通辺をもたず、和集合が $C_6$ の全六辺なので $M\triangle N=E(C_6)$ です。非孤立成分は偶cycle一つで、辺は
$$
12\in M, 23\in N, 34\in M, 45\in N, 56\in M, 61\in N
$$
と交互に並びます。各matchingの辺は3本で、反転しても大きさは変わりません。□
matching $M=\{x_2y_1,x_3y_2\}$ とpath
$$
x_1,y_1,x_2,y_2,x_3,y_3
$$
が与えられたとする。必要な非matching辺を明記し、反転後のmatchingを書け。
必要な非matching辺は
$$
x_1y_1,\quad x_2y_2,\quad x_3y_3
$$
です。$x_1,y_3$ が未飽和ならaugmenting pathで、反転後は
$$
M'=\{x_1y_1,x_2y_2,x_3y_3\}
$$
となり、辺数は2から3へ増えます。□
$$
N(a)=N(b)=N(c)=\{1,2\},\qquad N(d)=\{3,4\}
$$
で、matching $M=\{a1,b2,d3\}$ から未飽和頂点 $c$ を根に交互探索する。到達集合 $Z_X,Z_Y$ を求めよ。
$c$ から1,2へ到達し、それらのmatching相手 $a,b$ へ到達します。$a,b$ の近傍から新しい頂点は出ないので
$$
Z_X=\{a,b,c\},\qquad Z_Y=\{1,2\}.
$$
従って $N(Z_X)=Z_Y$ かつ $2<3$ で、Hall障害です。□
$M\triangle N$ の一成分がalternating pathであるとき、その両端の辺種類により $|M\cap E(P)|-|N\cap E(P)|$ を分類せよ。
両端がともに $M$-辺なら $M$-辺が一本多く、差は1です。両端の種類が異なれば同数で差は0です。両端がともに $N$-辺なら $N$-辺が一本多く、差は $-1$ です。これは交互列を端から書けば直ちに確認できます。□
空matchingから反復augmenting算法を $K_{p,q}$ に適用する。停止時のmatching辺数とaugmenting回数を求めよ。また $p\le q$ のとき長さ1のpathだけを選び続けられることを示せ。
maximum matchingの大きさは小さい部の頂点数
$$
\min(p,q)
$$
であり、空から一回ごとに1増えるため反復回数も同じです。
$p\le q$ とし、現在の大きさを $k< p$ とします。両側に未飽和頂点があり、完全二部グラフではその二頂点間に辺があります。この一辺自体が長さ1のaugmenting pathなので、毎回そのようなpathを選べます。□
本章で得たもの
augmenting pathの反転はmatchingを一つ増やします。二つのmatchingのsymmetric differenceがalternating pathと偶cycleへ分解されるため、augmenting pathがないことはmaximumであることと同値です。
二部グラフでは交互BFSによりpathを見つけられ、反復すればmaximum matchingが得られます。探索が失敗した場合も、到達集合が $|N(S)|<|S|$ を満たすHall障害を返します。
Mathpediaは寄付と、参考文献の書籍リンク（Amazonアソシエイト）の紹介料で運営されています。 支援について ／ 寄付する
