この章では最大マッチングに関する定理を見ていきましょう！

これらの定理は次章で最大マッチングを発見するアルゴリズムの正当性の証明に使います。

ベルジュの定理(Berge’s theorem)

それでは証明を見ていきましょう。割と簡単です。

\(\Rightarrow\,\)に関しては当たり前ですね。

なぜなら，もしも\(\,M\text{-}\)増大道が存在してしまったら前節で解説したように，
その増大道上の\(\,M\,\)の包含関係を反転させることで，\(M\,\)より大きいマッチングが得られてしまい，\(M\,\)の最大性に矛盾してしまうからですね。

よって後は\(\,\Leftarrow\,\)を示せばいいですね。そのために\(\,G\,\)には\(\,M\text{-}\)増大道が存在しないと仮定します。

背理法により示すために\(\,M\,\)は最大マッチングでないと仮定しましょう。

このとき\(\,G\,\)の最大マッチングを\(\,M’\,\)とおくと，もちろん\(\,|M’|\gt |M|\,\)です。

ここで対称差\(\,M\bigtriangleup M’\,\)^※1によって誘導された辺誘導部分グラフ\(\,G[M\bigtriangleup M’]\,\)^※2について考えます。

\(M\,\)が最大マッチング\(\,M’\,\)とどれほど異なるのかを考えている感じですね。

このときマッチングの定義より\(\,G[M\bigtriangleup M’]\,\)の各頂点は，
\(M,M’\,\)の辺それぞれに対して高々\(\,1\,\)本のみしか接続できません。

そのため\(\,G[M\bigtriangleup M’]\,\)の各頂点は次数が高々\(\,2\,\)以下です。

よって\(\,G[M\bigtriangleup M’]\,\)の各連結成分は道か閉路になることが分かります。

さらにグラフが対称差\(\,M\bigtriangleup M’\,\)から辺誘導されていることと，マッチングの定義に気をつければ，

これらの道や閉路は\(\,M,M’\,\)の辺が交互に出現するようなものであることが分かります(下図)。

※赤い辺を\(\,M’\,\)の辺，青い辺を\(\,M\,\)の辺として考えてください。

このときに出現する\(\,M’,M\,\)の辺の数について，

閉路\(\,\to\,\)同数，道\(\,\to\,\)同数orどちらか一方が\(\,1\,\)本多い

となります。

ここで\(\,|M’|\gt |M|\,\)より，\(\,M’\,\)の辺の本数の方が多くなければなりませんでした。

そのため道の端の辺が\(\,M’\,\)によって飽和されている道が少なくとも\(\,1\,\)つは存在する必要があります
(上の図の道のグラフのようなものです)。

これは\(\,M\text{-}\)増大道であり，\(\,M\text{-}\)増大道が存在しないことに矛盾します。

したがって背理法により，\(\,\Leftarrow\,\)が示されたのでベルジュの定理は示されました。\(\quad\square\)

余談ですが，この証明方法と同様にして「木の完全マッチングは存在すればただ一つである」ことなどマッチングに関する様々な命題を証明できるので，理解しておくと便利です。

※1 集合\(\,A,B\,\)の対称差とは\(A\bigtriangleup B \coloneqq (A-B)\cup(B-A)\,\)のことです。
分かりやすく言えば，\(\,A,B\,\)のどちらか一方のみに属するものの集合です。

※2 \(G\,\)の辺の集合\(\,S\,\)について辺誘導部分グラフ\(\,G[S]\,\)とは，頂点集合が\(\,S\,\)の端点，辺集合が\(\,S\,\)となる\(\,G\,\)の部分グラフのことです。
分かりやすく言えば，辺の集合\(\,S\,\)の情報だけ抜き出したグラフです。

ケーニヒ-オレの公式(König-Ore formula)

それでは証明です。不等式で評価することで証明します。

ここで\(\,\displaystyle d\coloneqq \max_{S\sub X}\{|S|-|N_G(S)|\}\,\)とおき，

さらに\(\,S_0 \sub X\,\)を\(\,d= |S_0|-|N_G(S_0)|\,\)となるように選びます。

定理を示すには\(\,|M|\leq |X|-d\,\)と\(\,|M|\geq |X|-d\,\)を示せば良いですね。

まずは簡単な\(\,\leq\,\)を示していきます。

このとき以下のように式変形できます。

よって\(\,\leq\,\)は示されました。

続いて\(\,\geq\,\)を示していきましょう。

ややトリッキーな証明です。

\(G(X,Y)\,\)の部集合\(\,X\,\)に新たに位数\(\,d\,\)の頂点集合\(\,D\,\)を追加します。

そして\(\,X\,\)と\(\,D\,\)の頂点間に全て辺を結ぶことで，
新たな\(\,2\,\)部グラフ\(\,H=H(X,Y\cup D)\,\)を構成します。

この\(\,2\,\)部グラフ\(\,H\,\)において，任意の\(\,S\subset X\,\)について考えると次の式変形が成り立ちます。

つまり\(\,2\,\)部グラフ\(\,H(X,Y\cup D)\,\)において

「\(\,X\,\)の任意の部分集合\(\,S\not=\emptyset\,\)について\(\,|N_H(S)|\geq |S|\,\)が成り立つ」ので

ホールの結婚定理よりグラフ\(\,H\,\)は\(\,X\,\)の全ての頂点を飽和するマッチング\(\,M_H\,\)を持ちます。

\(M_H\,\)から頂点集合\(\,D\,\)に接続する辺を除いた辺集合\(\,M_G\,\)は\(\,G\,\)のマッチングとなり，

\(M_H\,\)が\(\,X\,\)の全ての頂点を飽和するので，\(\,|M_G|\geq|M_H|-|D|=|X|-d\,\)です。

よって\(\,M\,\)の最大性から\(\,|M|\geq |X|-d\,\)となり，\(\,\geq\,\)も示されました。

したがって\(\,\displaystyle |M|=|X|-\max_{S\sub X}\{|S|-|N_G(S)|\}\,\)は示されました。\(\quad\square\)

この定理のイメージは難しいですが簡単に言ってしまえば，

最大マッチング\(\,M\,\)においては\(\,\displaystyle \max_{S\sub X}\{|S|-|N_G(S)|\}\,\)が飽和されていない点の数に一致するという感じです。

どうしてそのようになるかは，\(\,M\,\)の最大性をもとに\(\,|S|-|N_G(S)|\,\)を最大化しようとすると，詳しくは省きますが\(\,M\,\)に飽和されていない点を\(\,S\,\)に含め，逆に\(\,N_G(S)\,\)には飽和されていない点を含めないようにした方が良いことによります。

あくまでイメージの議論ですので厳密ではありませんが，要望が多ければ改めて厳密に書き直したいと思います。

もしくは次章のアルゴリズムの正当性をケーニヒ-オレの公式を用いて証明するときに，具体的に\(\,|S|-|N_G(S)|\,\)が最大となるような\(\,S\,\)を構成している様子から，なんとなくそのことを感じ取れると思います。

複雑なアルゴリズムのように見えますが，やってみると非常に単純なことをしています。

ベルジュの定理より，\(\,M\,\)が最大マッチングでないときは\(\,M\text{-}\)増大道が存在します。

そこで\(\,M\,\)に飽和されていない頂点からなる集合\(\,X_0\,\)から，

交互道を下図のように\(\,Y_1,X_1,\ldots,\,\)と伸ばしていき，増大道を探しているということですね。

※赤の辺は\(\,M\,\)に属していることを表す。

例えば上のグラフでは点\(\,x,y\,\)が\(\,M\,\)によって飽和されていないので，
\(X_0,Y_1,X_1,\ldots,Y_3\,\)から一つずつ点を取ることで\(\,x\,\)から\(\,y\,\)までの増大道が取れますね。

そして増大道を探せなくなったときが\(\,Y_k=\emptyset\,\)に対応し，
再びベルジュの定理より，最大マッチングを見つけたので探索終了というイメージですね。

ここまで述べたイメージを厳密に議論することで，
上のアルゴリズムの正当性を証明しておきましょう。

集合\(\,X_i,Y_i\,\)の存在は空集合\(\,\emptyset\,\)も認めているため常に大丈夫です。

そのため正当性の証明として示すべきことは

\((\,\mathrm{i}\,)\,\)手順\(\,[5]\,\)で\(\,M\,\)で飽和されていない頂点が出現した場合に，その頂点までの\(\,M\text{-}\)増大道を取ることができること

\((\,\mathrm{ii}\,)\,\)\(\,Y_{k}=\emptyset\,\)となった場合に\(\,M\,\)自身が最大マッチングであること

の\(\,2\,\)つを示せば良いです。

しかし\(\,(\,\mathrm{i}\,)\,\)については，上のグラフで\(\,x\,\)から\(\,y\,\)までの増大道取ったのと同様なので明らかですね。

そのため\(\,(\,\mathrm{ii}\,)\,\)について示せばOKです。

背理法によって示すために，ある\(\,k\geq 1\,\)で\(\,Y_{k}=\emptyset\,\)となっているのに，\(\,M\,\)は最大マッチングでないと仮定しましょう。

このときベルジュの定理より増大道\(\,P\,\)が取れます。

\(2\,\)部グラフの増大道なので端点の一方は\(\,X\,\)に属し，もう一方は\(\,Y\,\)に属します(先程のグラフを見ると分かりやすいでしょう)。

そのため始点を\(\,x’\in X\)，終点を\(\,y’\in Y\,\)と置いてもよいです。

\(P\,\)は増大道のため端点\(\,x’,y’\,\)は\(\,M\,\)によって飽和されていません。

そのため\(\,x’\in X_0\,\)です。

よって手順を行っていくと，ある\(\,l\geq 1\,\)で\(\,y’\in Y_l\,\)となります。

今\(\,k\,\)で\(\,Y_{k}=\emptyset\,\)となり手順が終了しているので，\(\,k\lt l\,\)となる必要があります。

しかしこのとき\(\,l\,\)の時点で\(\,Y_{l}\,\)に\(\,M\,\)で飽和されていない点\(\,y’\,\)が存在するので，
本来はそこで\(\,M\,\)の修正を行うはずなのに行われていないことになります。

つまりアルゴリズムの手順に矛盾するので，背理法より\(\,(\,\mathrm{ii}\,)\,\)は示されました。\(\quad\square\)

ちなみに上で紹介したケーニヒ-オレの公式を用いても\(\,(\,\mathrm{ii}\,)\,\)を示すことができます。

まず\(\,S=X_0\cup X_1 \cup \cdots\cup X_{k-1},\,\,T=Y_1\cup Y_2\cup\cdots \cup Y_{k-1}\, \)とおきます。

このとき\(\,Y_k=\emptyset\,\)，
つまり\(\,N_G(X_{k-1})\cap T^{c}=\emptyset\Leftrightarrow N_G(X_{k-1})\subset T\,\)より

\(N_G(S)=T\,\)が分かります。

\(k=3\,\)の場合を表した下のグラフからも直感的に分かりやすいと思います。

またこれも上のグラフから直感的に分かりやすいですが，

より，\(\,N_M(T)=S-X_0\,\)が成り立ちます。

手順より\(\,Y_1,\ldots,Y_{k-1}\,\)に\(\,M\,\)によって飽和されていない点は存在しないので，\(\,T\,\)の点は全て\(\,M\,\)によって飽和されています。

そのためマッチングの一対一対応から

\(|S|-|X_0|=|N_M(T)|=|T|\,\)となります。

これと\(\,|N_G(S)|=|T|\,\)を合わせると

\(|X_0|=|S|-|N_G(S)|\,\)となります。

故に次の式変形が成り立ちます。

よって\(\,M\,\)が最大マッチングとなることが分かるので，証明終了です。\(\quad\square\)

今回の記事では最大マッチング(maximum matching)を解説いたしました。

かなりボリュームのある記事になったので，また改めてゆっくり読むことをおススメします。

もし「説明がわかりにくい」などご要望・ご感想がありましたら，
X（旧:Twitter）で#トイカラでつぶやいていただけると，できる限り対応します。

ここまで読んでいただき，ありがとうございました。

• \([1]\) J.A.ボンディ, U.S.R.マーティ著.山下登茂紀,千葉周也訳.”グラフ理論”.初版.丸善出版.2022出版.p.411-420.
• \([2]\) Jin Akiyama,Mikio Kano.”Factors and Factorizations of Graphs”.eBook 1st Edition.Springer.Published 2011.p.23,35-36