§E16.13二部マッチングと Kőnig の定理

最終更新

マッチングは、どの二辺も端点を共有しない辺集合である。辺数が最大のマッチングを求める問題に対して、二つの問いがある。第一に、手元のマッチングが最大であるかどうかを、他のすべてのマッチングと比べることなく判定する方法があるか。第二に、最大であるという主張を、それ以上大きいマッチングが無いことの証拠とともに述べる方法があるか。本記事では、有限二部グラフについて、この二つの問いに答える。

第一の問いには、交互道と増加道を用いて答える。マッチングに属する辺と属さない辺が交互に現れ、両端点がいずれもマッチングに被覆されていない道を増加道という。増加道に沿って辺の所属を入れ替えるとマッチングの辺数が一つ増えるので、マッチングが最大であれば増加道は存在しない。逆も成り立つ。したがって、増加道が存在しないことが最大性の判定条件になる。第二の問いには、頂点被覆を用いて答える。すべての辺の少なくとも一方の端点を含む頂点集合を頂点被覆という。頂点被覆の頂点数は、つねにマッチングの辺数以上である。したがって、辺数と頂点数が一致するマッチングと頂点被覆の対が見つかれば、両方の最適性が同時に確定する。二部グラフではこの対がつねに存在するというのが Kőnig の定理である。

本記事を通じて、G=(X⊔Y,E)G=(X\sqcup Y,E)は有限単純二部グラフとする。すなわち頂点集合は互いに交わらない二つの集合XXとYYの合併であり、各辺はXXの頂点とYYの頂点をちょうど一つずつ端点にもつ。多重辺とループは考えない。グラフの基本的な語彙は§D2.7 定義 1.1に、道は§D2.7 定義 2.1に従う。マッチングの定義は§D2.12 定義 1.1による。ここで再掲すると、辺集合M⊆EM\subseteq Eがマッチングであるとは、MMの相異なる二辺が端点を共有しないことをいう。MMのいずれかの辺の端点である頂点を、MMに被覆されるという。辺数∣M∣\lvert M\rvertが最大であるマッチングを最大マッチングといい、その辺数をν(G)\nu(G)と書く。ここでの最大は辺数についての最大であり、包含に関する極大とは異なる。辺{x,y}\{x,y\}をxyxyとも書く。

1 交互道と増加道

定義 1.1. 有限二部グラフG=(X⊔Y,E)G=(X\sqcup Y,E)とマッチングM⊆EM\subseteq Eをとる。MMに被覆されない頂点を MM-非飽和頂点 (M-unsaturated vertex) という。

GGの道v0,v1,…,vkv_0,v_1,\dots,v_kが MM-交互道 (M-alternating path) であるとは、辺vi−1viv_{i-1}v_i（1≤i≤k1\le i\le k）がMMに属するか属さないかがiiとともに交互に入れ替わることをいう。長さ00の道もMM-交互道とみなす。

MM-交互道v0,v1,…,vkv_0,v_1,\dots,v_kが MM-増加道 (M-augmenting path) であるとは、k≥1k\ge1であり、両方の端点v0v_0とvkv_kがいずれもMM-非飽和頂点であることをいう。

注意 1.2 (交互道の定義の違いについて).§D2.12 定義 1.1ではMM-交互道を、MMに被覆されない頂点から始まる交互な道として定義しており、始点に条件を課している。本記事の定義 1.1は始点に条件を課さないので、本記事のMM-交互道の方が広い。被覆されない頂点をよぶ語は、両記事ともMM-非飽和である。

MM-増加道については、長さが11以上である道に関して両者は一致する。実際、両端点が被覆されない交互な道は、始点が被覆されないので前者の意味でもMM-交互道であり、逆に前者の意味のMM-交互道は後者の意味でもMM-交互道だからである。本記事は長さ00の道をMM-増加道から明示的に除く。長さ00の道は辺をもたず、辺の所属を入れ替えてもマッチングの辺数が変わらないからである。

MM-増加道の定義から両端点が非飽和であるという条件を落とすと、後の特徴づけは成り立たない。実際、飽和した端点をもつ交互道に沿って辺の所属を入れ替えると、その端点がMMの二本の辺に接する場合が生じる。その場合には、得られる辺集合はマッチングにならない。

補題 1.3. 有限二部グラフGGのマッチングMMとMM-増加道P: v0,v1,…,vkP:\ v_0,v_1,\dots,v_kについて、kkは奇数である。さらにPPの辺のうちMMに属さないものは(k+1)/2(k+1)/2本、MMに属するものは(k−1)/2(k-1)/2本である。

証明. 両端点v0v_0とvkv_kはMM-非飽和であるから、v0v_0に接する辺v0v1v_0v_1とvkv_kに接する辺vk−1vkv_{k-1}v_kはいずれもMMに属さない。PPはMM-交互道であるから、辺vi−1viv_{i-1}v_iがMMに属するかどうかはiiとともに交互に入れ替わる。最初の辺v0v1v_0v_1がMMに属さないので、vi−1viv_{i-1}v_iがMMに属することとiiが偶数であることは同値である。最後の辺vk−1vkv_{k-1}v_kがMMに属さないのでkkは奇数である。

1≤i≤k1\le i\le kのうちiiが奇数であるものは(k+1)/2(k+1)/2個、偶数であるものは(k−1)/2(k-1)/2個であるから、MMに属さない辺は(k+1)/2(k+1)/2本、MMに属する辺は(k−1)/2(k-1)/2本である。▨

特徴づけの証明では、二つのマッチングの対称差がどのような形をしているかを用いる。対称差に属する辺のうち各頂点に接するものは二本以下であるので、次の補題により、対称差を辺集合とするグラフの形が決まる。

補題 1.4. 有限グラフHHのすべての頂点の次数が22以下であるとする。このときHHの各連結成分KKについて、次のいずれかが成り立つ。

  1. KKの頂点をu0,u1,…,uru_0,u_1,\dots,u_r（r≥0r\ge0）と並べて、KKの辺全体が{ui−1ui: 1≤i≤r}\{u_{i-1}u_i:\ 1\le i\le r\}に一致するようにすることができる。このときKKは道である。
  2. KKの頂点をu0,u1,…,uru_0,u_1,\dots,u_r（r≥2r\ge2）と並べて、KKの辺全体が{ui−1ui: 1≤i≤r}∪{uru0}\{u_{i-1}u_i:\ 1\le i\le r\}\cup\{u_ru_0\}に一致するようにすることができる。このときKKは閉路である。

証明.KKをHHの連結成分とする。KKの頂点は有限個であるから、KKに含まれる道の長さは有界であり、長さが最大である道P: u0,u1,…,urP:\ u_0,u_1,\dots,u_rが存在する。

r=0r=0の場合を先に扱う。u0u_0に隣接する頂点wwが存在すればu0,wu_0,wが長さ11の道となって最大性に反するので、u0u_0の次数は00である。KKは連結であるからKKはu0u_0だけからなり、主張 (1)が成り立つ。

以下r≥1r\ge1とする。u0u_0に隣接する頂点wwがPPに現れないと仮定すると、w,u0,u1,…,urw,u_0,u_1,\dots,u_rがPPより長い道となって最大性に反する。よってu0u_0に隣接する頂点はすべてPPに現れる。同じ理由で、uru_rに隣接する頂点もすべてPPに現れる。また、0<i<r0<i<rを満たすuiu_iはui−1u_{i-1}とui+1u_{i+1}に隣接し、次数が22以下であるから、これ以外の頂点には隣接しない。

u0u_0がu1u_1以外の頂点に隣接しない場合を考える。uru_rがur−1u_{r-1}以外の頂点に隣接すると仮定すると、その頂点はPPに現れるのでuju_j（0≤j≤r−20\le j\le r-2）と書くことができる。j=0j=0ならばu0u_0がu1u_1以外の頂点に隣接することになって仮定に反する。0<j0<jならばuju_jはuj−1u_{j-1}、uj+1u_{j+1}およびuru_rの三頂点に隣接し、次数が33になって仮定に反する。よってuru_rもur−1u_{r-1}以外の頂点に隣接しない。したがってPPのどの頂点もPPの辺以外の辺に接しない。KKは連結であるから、KKの頂点はすべてPPに現れ、KKの辺はPPの辺だけである。よって主張 (1)が成り立つ。

u0u_0がu1u_1以外の頂点uiu_iに隣接する場合を考える。自己ループが無いのでi≠0i\ne0であり、i≠1i\ne1であるからi≥2i\ge2である。i<ri<rと仮定すると、uiu_iはui−1u_{i-1}、ui+1u_{i+1}およびu0u_0の三頂点に隣接して次数が33になり、仮定に反する。よってi=ri=rであり、r≥2r\ge2である。このときu0,u1,…,ur,u0u_0,u_1,\dots,u_r,u_0は閉路である。この閉路に現れる各頂点は既に二つの頂点に隣接しているので、次数が22以下であることからこれ以外の頂点には隣接しない。KKは連結であるから、KKの頂点はすべてこの閉路に現れ、KKの辺はこの閉路の辺だけである。よって主張 (2)が成り立つ。▨

1.1 証明方針

増加道が存在すれば最大でないことは、増加道に沿って辺の所属を入れ替えた辺集合を作り、その辺集合がマッチングであって辺数が一つ多いことを確かめれば従う。確かめる点は、入れ替えた後も各頂点が高々一本の辺に接することである。

逆向き、すなわち最大でなければ増加道が存在することが本質的である。辺数の大きいマッチングM′M'をとり、MMとM′M'の対称差を辺集合とする部分グラフHHを考える。各頂点はMMの辺に高々一本、M′M'の辺に高々一本しか接しないので、HHにおける次数は22以下であり、補題 1.4によりHHの各連結成分は道か閉路である。HHの辺はMMとM′M'に交互に属するから、閉路成分は両者を同数含む。M′M'の辺の総数がMMの辺の総数より多いことから、M′M'の辺をMMの辺より多く含む成分が存在し、その成分は閉路ではなく、両端の辺がM′M'に属する道である。最後に、その道の両端点がMM-非飽和であることを確かめる。ここで、端点がMMとM′M'の共通の辺で被覆されている可能性を排除する必要がある。

定理 1.5. 有限二部グラフGGのマッチングMMについて、MMが最大マッチングであることと、MM-増加道が存在しないことは同値である。

証明. 増加道が存在すれば最大でないこと。MM-増加道P: v0,v1,…,vkP:\ v_0,v_1,\dots,v_kをとる。補題 1.3によりkkは奇数であり、PPの辺のうちMMに属さないものが(k+1)/2(k+1)/2本、属するものが(k−1)/2(k-1)/2本である。PPの辺集合をE(P)E(P)と書き、

M′=(M∖E(P))∪(E(P)∖M)M'=(M\setminus E(P))\cup(E(P)\setminus M)

と置く。M′M'がマッチングであることを示す。頂点wwをとる。wwがPPに現れないならば、wwに接するM′M'の辺はwwに接するMMの辺と同じであるから高々一本である。wwがPPの内部の頂点viv_i（0<i<k0<i<k）であるならば、wwに接するPPの辺はちょうど二本vi−1viv_{i-1}v_iとvivi+1v_iv_{i+1}であり、交互性によりそのうち一本がMMに属し他方が属さない。したがってM′M'では、MMに属していた方が外れ、属していなかった方が入るので、wwに接するPPの辺のうちM′M'に属するものはちょうど一本である。さらに、PPに現れない辺でwwに接しMMに属するものは存在しない。もし存在すれば、wwはPP上のMMの辺と合わせてMMの二本の辺に接することになり、MMがマッチングであることに反する。wwが端点v0v_0またはvkv_kであるならば、wwはMM-非飽和であるからMMの辺に接しておらず、M′M'ではPP上のMMに属さない辺一本だけに接する。以上よりM′M'はマッチングである。辺数は

∣M′∣=∣M∣−k−12+k+12=∣M∣+1\lvert M'\rvert=\lvert M\rvert-\frac{k-1}{2}+\frac{k+1}{2}=\lvert M\rvert+1

であるから、MMは最大マッチングではない。

最大でなければ増加道が存在すること。MMが最大でないとし、∣M′∣>∣M∣\lvert M'\rvert>\lvert M\rvertを満たすマッチングM′M'をとる。辺集合

D=(M∖M′)∪(M′∖M)D=(M\setminus M')\cup(M'\setminus M)

と、DDの辺の端点全体を頂点集合とする部分グラフHHを考える。HHの各頂点は、MMの辺に高々一本、M′M'の辺に高々一本しか接しないので、HHにおける次数は11または22である。したがって補題 1.4により、HHの各連結成分は道または閉路である。また、HHにおいて同じ頂点に接する二本の辺が同時にMMに属することはなく、同時にM′M'に属することもないから、道または閉路に沿って辺はM∖M′M\setminus M'とM′∖MM'\setminus Mに交互に属する。とくに各成分はMM-交互道またはMM-交互な閉路である。

閉路成分の長さが偶数であることを示す。閉路を一周すると辺の属する側が一本ごとに入れ替わる。長さが奇数であるとすると、一周して戻ったところで同じ側の二本の辺が一つの頂点に接することになり、その頂点がMMの二本の辺に接するかM′M'の二本の辺に接することになって、マッチングであることに反する。よって閉路成分の長さは偶数であり、MMの辺とM′M'の辺を同数含む。∣M′∖M∣=∣M′∣−∣M∩M′∣>∣M∣−∣M∩M′∣=∣M∖M′∣\lvert M'\setminus M\rvert=\lvert M'\rvert-\lvert M\cap M'\rvert>\lvert M\rvert-\lvert M\cap M'\rvert=\lvert M\setminus M'\rvertであるから、HH全体ではM′M'の辺がMMの辺より多い。ゆえにM′M'の辺をMMの辺より多く含む成分が存在し、それは閉路ではなく道である。その道をQQとする。QQの辺はM∖M′M\setminus M'とM′∖MM'\setminus Mに交互に属するので、両者の本数の差は11以下である。QQはM′M'の辺をMMの辺より多く含むから、差はちょうど11であり、QQの長さは奇数で、QQの両端の辺はいずれもM′∖MM'\setminus Mに属する。

QQの端点wwがMM-非飽和であることを示す。wwに接するHHの辺はQQの端の辺ただ一本であり、それはM′∖MM'\setminus Mに属する。wwがMMに被覆されていると仮定し、その辺をe∈Me\in Mとする。eeはHHの辺ではないのでe∈M∩M′e\in M\cap M'である。するとwwはM′M'の二本の辺、すなわちeeとQQの端の辺に接することになり、M′M'がマッチングであることに反する。よってwwはMM-非飽和である。もう一方の端点についても同じ議論が成り立つ。

したがってQQは両端点がMM-非飽和であるMM-交互道であり、長さは11以上であるからMM-増加道である。▨

増加道による特徴づけにより、マッチングが最大であるかどうかは、有限個の道の中から増加道を探すことによって判定することができる。次の命題では、この探索を繰り返す手続きが最大マッチングを与えることが述べられる。

命題 1.6. 有限二部グラフG=(X⊔Y,E)G=(X\sqcup Y,E)について、M=∅M=\emptysetから出発し、MM-増加道が存在するかぎり一つ選んで定理 1.5の証明にある入れ替えを行い、その結果を新しいMMとする手続きを考える。この手続きは高々min⁡{∣X∣,∣Y∣}\min\{\lvert X\rvert,\lvert Y\rvert\}回の反復で停止し、停止時のMMは最大マッチングである。

証明. ループ不変条件（§D2.8 定義 1.1）として「MMはマッチングである」をとる。初期化ではM=∅M=\emptysetがマッチングであるから成り立つ。維持は定理 1.5の証明の前半が与える。すなわちMM-増加道に沿う入れ替えの結果はマッチングであり、辺数はちょうど11増える。

停止性を示す。マッチングの各辺はXXの相異なる頂点とYYの相異なる頂点を用いるから、任意のマッチングの辺数はmin⁡{∣X∣,∣Y∣}\min\{\lvert X\rvert,\lvert Y\rvert\}以下である。m=min⁡{∣X∣,∣Y∣}m=\min\{\lvert X\rvert,\lvert Y\rvert\}と置き、ループの状態に対して変量V=m−∣M∣V=m-\lvert M\rvertを定めると、VVは非負整数であり、本体を一度実行するたびに∣M∣\lvert M\rvertが11増えるので狭義に減少する。§D2.8 命題 1.4により手続きは有限回で停止し、VVの初期値がmmであるから反復回数はmm以下である。

停止時にはループの継続条件が偽であり、MM-増加道が存在しない。不変条件によりMMはマッチングであるから、定理 1.5によりMMは最大マッチングである。この形の議論が正当性を与えることは§D2.8 定理 1.2による。▨

2 頂点被覆と弱い向きの不等式

定義 2.1. 有限二部グラフG=(X⊔Y,E)G=(X\sqcup Y,E)について、頂点集合C⊆X⊔YC\subseteq X\sqcup Yが頂点被覆 (vertex cover) であるとは、EEのすべての辺が少なくとも一方の端点をCCにもつことをいう。頂点数∣C∣\lvert C\rvertが最小である頂点被覆の頂点数をτ(G)\tau(G)と書く。ここでの最小は頂点数についての最小であり、包含に関する極小とは異なる。

命題 2.2. 有限二部グラフGGについてν(G)≤τ(G)\nu(G)\le\tau(G)が成り立つ。

証明.MMをマッチング、CCを頂点被覆とする。MMの各辺eeは少なくとも一方の端点をCCにもつので、その端点の一つを選んでψ(e)∈C\psi(e)\in Cと定める。MMの相異なる二辺は端点を共有しないから、ψ\psiは単射である。よって∣M∣≤∣C∣\lvert M\rvert\le\lvert C\rvertが成り立つ。MMを最大マッチング、CCを頂点数が最小の頂点被覆にとるとν(G)≤τ(G)\nu(G)\le\tau(G)を得る。▨

3 Kőnig の定理

命題 2.2により、頂点数がν(G)\nu(G)に等しい頂点被覆を一つ構成すれば、等式ν(G)=τ(G)\nu(G)=\tau(G)が従う。このとき、マッチングと頂点被覆の最適性が同時に確定する。この構成には、最大マッチングMMを用いる。XXのMM-非飽和頂点全体をUUとし、UUの頂点から出発して最初の辺がMMに属さないMM-交互道でたどり着くことのできる頂点全体をZZとする。二部グラフでは、このような交互道はXXの頂点からMMに属さない辺でYYへ移り、MMの辺でXXへ戻る、という往復を繰り返す。したがってZ∩YZ\cap Yの頂点はMMに属さない辺で到達され、UUに属さないZ∩XZ\cap Xの頂点はMMの辺で到達される。次の補題では、ZZの頂点と、その頂点に接する辺との関係を三つの主張として述べる。

補題 3.1. 有限二部グラフG=(X⊔Y,E)G=(X\sqcup Y,E)の最大マッチングをMMとし、XXのMM-非飽和頂点全体をUUとする。頂点vvが UUから交互に到達可能であるとは、あるu∈Uu\in UからvvへのMM-交互道であって、長さが00であるか最初の辺がMMに属さないものが存在することをいう。UUから交互に到達可能な頂点全体をZZと書く。このとき次の三つが成り立つ。

  1. x∈Z∩Xx\in Z\cap Xかつx∉Ux\notin Uならば、xxはMMに被覆され、xxを被覆するMMの辺の他方の端点はZ∩YZ\cap Yに属する。
  2. y∈Z∩Yy\in Z\cap Yならば、yyはMMに被覆され、yyを被覆するMMの辺の他方の端点はZ∩XZ\cap Xに属する。
  3. x∈Z∩Xx\in Z\cap Xかつxy∈E∖Mxy\in E\setminus Mならばy∈Zy\in Zである。

証明. まずZZの定義に現れる道の形を確かめる。u∈Uu\in Uから出発し最初の辺がMMに属さないMM-交互道u=v0,v1,…,vku=v_0,v_1,\dots,v_kをとる。交互性により、辺vi−1viv_{i-1}v_iはiiが偶数のときMMに属し、iiが奇数のときMMに属さない。u∈Xu\in Xであり各辺がXXとYYをまたぐので、viv_iはiiが偶数のときXXに、奇数のときYYに属する。したがって、終点がYYに属するときはkkが奇数で最後の辺はMMに属さず、終点がXXに属するときはkkが偶数で、k≥2k\ge2ならば最後の辺はMMに属する。また、この道の始点側の部分列v0,…,vjv_0,\dots,v_jは再び同じ条件を満たすMM-交互道であるから、道に現れるすべての頂点はZZに属する。

主張 (1)を示す。x∈Z∩Xx\in Z\cap Xかつx∉Ux\notin Uとする。xxへ至る上の形の道v0,…,vkv_0,\dots,v_kをとると、kkは偶数である。k=0k=0ならばx=u∈Ux=u\in Uとなって仮定に反するのでk≥2k\ge2であり、最後の辺vk−1vk=vk−1xv_{k-1}v_k=v_{k-1}xはMMに属する。よってxxはMMに被覆され、その辺の他方の端点vk−1v_{k-1}は道上の頂点であるからZZに属し、k−1k-1が奇数であるからYYに属する。

主張 (2)を示す。y∈Z∩Yy\in Z\cap Yとし、yyへ至る上の形の道P: v0,…,vkP:\ v_0,\dots,v_kをとる。kkは奇数であり、最後の辺はMMに属さない。

yyがMM-非飽和であると仮定する。PPの始点v0=uv_0=uはUUに属するのでMM-非飽和であり、k≥1k\ge1であるから、PPは両端点がいずれもMM-非飽和であるMM-交互道、すなわちMM-増加道である。これはMMが最大マッチングであることと定理 1.5に反する。よってyyはMMに被覆される。

yyを被覆するMMの辺をxyxyとする。x∈Xx\in Xである。xxがPPに現れるならば、上に述べたとおりx∈Zx\in Zである。xxがPPに現れないならば、PPの末尾に辺yxyxを付け加えた列v0,…,vk,xv_0,\dots,v_k,xは頂点がすべて相異なるので道であり、PPの最後の辺がMMに属さずyxyxがMMに属するので交互性も保たれる。よってこの道はZZの定義の条件を満たし、x∈Zx\in Zである。いずれの場合もx∈Z∩Xx\in Z\cap Xとなる。

主張 (3)を示す。x∈Z∩Xx\in Z\cap Xかつxy∈E∖Mxy\in E\setminus Mとする。xxへ至る上の形の道P: v0,…,vkP:\ v_0,\dots,v_kをとるとkkは偶数である。yyがPPに現れるならばy∈Zy\in Zである。yyがPPに現れないならば、列v0,…,vk,yv_0,\dots,v_k,yは道である。k=0k=0のときこの道の最初の辺はxyxyでありMMに属さないので条件を満たし、k≥2k\ge2のときPPの最後の辺はMMに属しxyxyは属さないので交互性が保たれる。いずれの場合もy∈Zy\in Zである。▨

3.1 証明方針

構成する頂点被覆は

C=(X∖Z)∪(Y∩Z)C=(X\setminus Z)\cup(Y\cap Z)

である。示すべきことは二つあり、それぞれ別に証明する。

第一に、CCが頂点被覆であること、すなわちx∈Zx\in Zかつy∉Zy\notin Zを満たす辺xyxyが存在しないことである。ここでは辺がMMに属する場合と属さない場合に分け、前者に主張 (1)を、後者に主張 (3)を用いる。

第二に、∣C∣≤∣M∣\lvert C\rvert\le\lvert M\rvertであることである。そのために、CCの各頂点をその頂点を被覆するMMの辺へ写す対応が定まり、しかも単射であることを示す。対応が定まることには、X∖ZX\setminus Zの頂点が非飽和ならばUUに属してZZに属することと、Y∩ZY\cap Zの頂点が飽和するという主張 (2)を用いる。単射であることには、XX側の頂点とYY側の頂点が同じ辺へ写る場合を排除する必要があり、そこで再び主張 (2)を用いる。

最後に、定理 3.2 (1)と定理 3.2 (2)から得られる不等式と命題 2.2の不等式を並べると、不等号の連鎖がすべて等号になり、ν(G)=τ(G)\nu(G)=\tau(G)が従う。

定理 3.2 (Kőnig の定理). 有限二部グラフGGについて、最大マッチングの辺数と最小頂点被覆の頂点数は等しい。すなわちν(G)=τ(G)\nu(G)=\tau(G)が成り立つ。

証明. 最大マッチングMMをとる。UUとZZを補題 3.1のとおりに定め、

C=(X∖Z)∪(Y∩Z)C=(X\setminus Z)\cup(Y\cap Z)

と置く。XXとYYは交わらないので、この合併は交わらない二つの集合の合併である。

  1. CCは頂点被覆である。辺xy∈Exy\in E（x∈Xx\in X、y∈Yy\in Y）をとり、x∉Cx\notin Cかつy∉Cy\notin Cであると仮定する。x∉X∖Zx\notin X\setminus Zよりx∈Zx\in Zであり、y∉Y∩Zy\notin Y\cap Zよりy∉Zy\notin Zである。

    xy∉Mxy\notin Mの場合、補題 3.1 (3)によりy∈Zy\in Zとなり、y∉Zy\notin Zに反する。

    xy∈Mxy\in Mの場合、xxはMMに被覆されるのでx∉Ux\notin Uである。補題 3.1 (1)により、xxを被覆するMMの辺の他方の端点がZZに属する。MMはマッチングであるからxxを被覆するMMの辺はxyxyただ一本であり、その他方の端点はyyである。よってy∈Zy\in Zとなり、y∉Zy\notin Zに反する。

    いずれの場合も矛盾するので、EEのすべての辺は少なくとも一方の端点をCCにもつ。よってCCは頂点被覆である。

  2. ∣C∣≤∣M∣\lvert C\rvert\le\lvert M\rvertである。まずCCの各頂点がMMに被覆されることを示す。x∈X∖Zx\in X\setminus ZがMM-非飽和であるとするとx∈Ux\in Uであり、長さ00の道によりx∈Zx\in Zとなってx∉Zx\notin Zに反する。よってX∖ZX\setminus Zの頂点はMMに被覆される。Y∩ZY\cap Zの頂点がMMに被覆されることは補題 3.1 (2)による。

    そこで、CCの各頂点vvに対し、vvを被覆するMMの辺φ(v)\varphi(v)を対応させる。MMはマッチングであるから、vvを被覆するMMの辺はただ一本であり、φ\varphiは矛盾なく定まる。φ\varphiが単射であることを示す。φ(v)=φ(v′)=e\varphi(v)=\varphi(v')=eかつv≠v′v\ne v'とすると、vvとv′v'はともにeeの端点であるから、一方がXXに、他方がYYに属する。XXに属する方をxx、YYに属する方をyyとすると、x∈X∖Zx\in X\setminus Zかつy∈Y∩Zy\in Y\cap Zかつxy=e∈Mxy=e\in Mである。ところが補題 3.1 (2)により、yyを被覆するMMの辺の他方の端点はZZに属するのでx∈Zx\in Zとなり、x∉Zx\notin Zに反する。よってφ\varphiは単射であり∣C∣≤∣M∣\lvert C\rvert\le\lvert M\rvertが成り立つ。

結論。MMは最大マッチングであるから∣M∣=ν(G)\lvert M\rvert=\nu(G)である。CCは頂点被覆であるからτ(G)≤∣C∣\tau(G)\le\lvert C\rvertである。(2)と命題 2.2を合わせると

τ(G)≤∣C∣≤∣M∣=ν(G)≤τ(G)\tau(G)\le\lvert C\rvert\le\lvert M\rvert=\nu(G)\le\tau(G)

となり、すべてが等号で結ばれる。よってν(G)=τ(G)\nu(G)=\tau(G)であり、あわせて∣C∣=∣M∣=ν(G)\lvert C\rvert=\lvert M\rvert=\nu(G)が得られる。▨

4 検算例

例 4.1.X={x1,x2,x3}X=\{x_1,x_2,x_3\}、Y={y1,y2,y3}Y=\{y_1,y_2,y_3\}とし、辺集合を

E={x1y1, x2y1, x3y1, x3y2, x3y3}E=\{x_1y_1,\ x_2y_1,\ x_3y_1,\ x_3y_2,\ x_3y_3\}

と定める。

最大マッチングの辺数。M={x1y1, x3y2}M=\{x_1y_1,\ x_3y_2\}はマッチングであるからν(G)≥2\nu(G)\ge2である。辺数33のマッチングが存在すると仮定すると、x1x_1、x2x_2、x3x_3のそれぞれが相異なるYYの頂点と組になる。ところがx1x_1に接する辺はx1y1x_1y_1だけ、x2x_2に接する辺はx2y1x_2y_1だけであるから、x1x_1とx2x_2はともにy1y_1と組になるほかなく、マッチングであることに反する。よってν(G)=2\nu(G)=2である。

構成による頂点被覆。上のM={x1y1, x3y2}M=\{x_1y_1,\ x_3y_2\}について、XXのMM-非飽和頂点はx2x_2だけであるからU={x2}U=\{x_2\}である。x2x_2から出発する交互道をたどる。x2x_2に接する辺はx2y1∉Mx_2y_1\notin Mだけであるからy1∈Zy_1\in Zである。y1y_1を被覆するMMの辺はx1y1x_1y_1であるからx1∈Zx_1\in Zである。x1x_1に接するMMに属さない辺は存在しない。よってZ={x2,y1,x1}Z=\{x_2,y_1,x_1\}である。したがって

C=(X∖Z)∪(Y∩Z)={x3}∪{y1}={x3,y1}C=(X\setminus Z)\cup(Y\cap Z)=\{x_3\}\cup\{y_1\}=\{x_3,y_1\}

となり∣C∣=2\lvert C\rvert=2である。CCが頂点被覆であることを辺ごとに確かめる。x1y1x_1y_1とx2y1x_2y_1とx3y1x_3y_1はy1y_1を含み、x3y2x_3y_2とx3y3x_3y_3はx3x_3を含む。よってすべての辺が覆われる。∣C∣=2=∣M∣\lvert C\rvert=2=\lvert M\rvertであり、定理 3.2のとおりν(G)=τ(G)=2\nu(G)=\tau(G)=2である。

Hall の条件との関係。S={x1,x2}S=\{x_1,x_2\}をとるとN(S)={y1}N(S)=\{y_1\}であり∣N(S)∣=1<2=∣S∣\lvert N(S)\rvert=1<2=\lvert S\rvertである。したがって§D2.12 定理 1.3の Hall の条件は成り立たず、XXのすべての頂点を被覆するマッチングは存在しない。これはν(G)=2<3=∣X∣\nu(G)=2<3=\lvert X\rvertと整合する。

5 演習

問題 5.1.

  1. MMとM′M'を有限二部グラフGGのマッチングとし、d=∣M′∣−∣M∣≥1d=\lvert M'\rvert-\lvert M\rvert\ge1とする。どの二本も頂点を共有しないdd本のMM-増加道が存在することを示せ。とくに、最大マッチングでない任意のマッチングMMに対し、どの二本も頂点を共有しないν(G)−∣M∣\nu(G)-\lvert M\rvert本のMM-増加道が存在することを示せ。
  2. 定義 1.1において、MM-増加道の定義から「両方の端点が非飽和である」という条件を落とし、「一方の端点が非飽和である」に置き換えたとする。この条件のもとで定理 1.5が成り立たなくなることを、頂点数33の二部グラフとその最大マッチングを用いた反例で示せ。
  3. MMを有限二部グラフG=(X⊔Y,E)G=(X\sqcup Y,E)の最大とは限らないマッチングとし、XXのMM-非飽和頂点全体をUUとする。UUから交互に到達可能な頂点全体ZZを補題 3.1と同じ文言で定め、C=(X∖Z)∪(Y∩Z)C=(X\setminus Z)\cup(Y\cap Z)と置く。CCが頂点被覆であることを示せ。さらに、MMが最大マッチングであることと、Y∩ZY\cap ZがMM-非飽和頂点を含まないことが同値であることを示せ。
  4. 有限二部グラフG=(X⊔Y,E)G=(X\sqcup Y,E)の頂点の次数の最大値をΔ\Deltaとし、Δ≥1\Delta\ge1とする。定理 3.2を用いてν(G)≥∣E∣/Δ\nu(G)\ge\lvert E\rvert/\Deltaを示せ。これを用いて、正の整数kkについてすべての頂点の次数がkkである有限二部グラフG=(X⊔Y,E)G=(X\sqcup Y,E)では∣X∣=∣Y∣\lvert X\rvert=\lvert Y\rvertであり、すべての頂点を被覆するマッチングが存在することを示せ。
  5. マッチング、頂点被覆、ν(G)\nu(G)、τ(G)\tau(G)を、二部性の条件を除いた同じ文言で有限単純グラフGGに対して定める。正の整数mmについて、頂点c0,c1,…,c2mc_0,c_1,\dots,c_{2m}と辺c0c1,c1c2,…,c2m−1c2m,c2mc0c_0c_1,c_1c_2,\dots,c_{2m-1}c_{2m},c_{2m}c_0からなる長さ2m+12m+1の閉路GmG_mではν(Gm)=m\nu(G_m)=mかつτ(Gm)=m+1\tau(G_m)=m+1であることを示せ。さらに、任意の有限単純グラフGGについてν(G)≤τ(G)≤2ν(G)\nu(G)\le\tau(G)\le2\nu(G)が成り立つことを示し、m=1m=1のとき右側の不等式が等号で成り立つことを確かめよ。
解答.

(1)を示す。辺集合D=(M∖M′)∪(M′∖M)D=(M\setminus M')\cup(M'\setminus M)と、DDの辺の端点全体を頂点集合としDDを辺集合とする部分グラフHHを考える。HHの各頂点はMMの辺に高々一本、M′M'の辺に高々一本しか接しないので、HHにおける次数は11または22である。HHの同じ頂点に接する二本の辺は、MMとM′M'がマッチングであるから、一方がM∖M′M\setminus M'に、他方がM′∖MM'\setminus Mに属する。HHの連結成分KKについて、KKの辺のうちM′∖MM'\setminus Mに属するものの本数からM∖M′M\setminus M'に属するものの本数を引いた数をδ(K)\delta(K)と置く。

各連結成分KKは、補題 1.4により道または閉路である。KKの頂点を同補題のとおりにu0,…,uru_0,\dots,u_rと並べる。KKが道であるとき、KKの頂点の次数は11以上であるからr≥1r\ge1であり、辺ei=ui−1uie_i=u_{i-1}u_i（1≤i≤r1\le i\le r）についてeie_iとei+1e_{i+1}はuiu_iを共有するので、e1,…,ere_1,\dots,e_rはM∖M′M\setminus M'とM′∖MM'\setminus Mに交互に属する。ゆえにδ(K)∈{−1,0,1}\delta(K)\in\{-1,0,1\}であり、δ(K)=1\delta(K)=1であるのはrrが奇数でe1e_1とere_rがともにM′∖MM'\setminus Mに属するときに限る。KKが閉路であるとき、辺e1,…,ere_1,\dots,e_rとer+1=uru0e_{r+1}=u_ru_0を順にたどると、隣り合う二辺と、u0u_0を共有するer+1e_{r+1}とe1e_1が、それぞれ異なる側に属する。一周して属する側が交互に入れ替わるので辺数r+1r+1は偶数であり、δ(K)=0\delta(K)=0である。DDの辺は連結成分ごとに分かれるから

∑Kδ(K)=∣M′∖M∣−∣M∖M′∣=(∣M′∣−∣M∩M′∣)−(∣M∣−∣M∩M′∣)=d\sum_{K}\delta(K)=\lvert M'\setminus M\rvert-\lvert M\setminus M'\rvert=\bigl(\lvert M'\rvert-\lvert M\cap M'\rvert\bigr)-\bigl(\lvert M\rvert-\lvert M\cap M'\rvert\bigr)=d

である。各δ(K)\delta(K)は11以下であるから、δ(K)=1\delta(K)=1を満たす連結成分は少なくともdd個ある。

δ(K)=1\delta(K)=1を満たす連結成分KKは道u0,…,uru_0,\dots,u_rであり、辺がMMに属するか属さないかは交互に入れ替わるのでMM-交互道である。端点u0u_0がMM-非飽和であることを示す。u0u_0に接するHHの辺はe1e_1だけであり、e1∈M′∖Me_1\in M'\setminus Mである。u0u_0が辺e∈Me\in Mに被覆されると仮定する。e∈M∖M′e\in M\setminus M'ならばeeはu0u_0に接するHHの辺であるからe=e1e=e_1となり、e1∉Me_1\notin Mに反する。e∈M∩M′e\in M\cap M'ならば、e∈Me\in Mかつe1∉Me_1\notin Mよりe≠e1e\ne e_1であり、M′M'の相異なる二辺eeとe1e_1がu0u_0を共有してM′M'がマッチングであることに反する。よってu0u_0はMM-非飽和であり、同じ議論によりuru_rもMM-非飽和である。r≥1r\ge1であるからKKはMM-増加道である。相異なる連結成分は頂点を共有しないので、このような連結成分からdd個を選べば、どの二本も頂点を共有しないdd本のMM-増加道が得られる。

MMが最大マッチングでないとき、最大マッチングM′M'をとるとd=ν(G)−∣M∣≥1d=\nu(G)-\lvert M\rvert\ge1であるから、前段により、どの二本も頂点を共有しないν(G)−∣M∣\nu(G)-\lvert M\rvert本のMM-増加道が存在する。

(2)を示す。X={x}X=\{x\}、Y={y1,y2}Y=\{y_1,y_2\}、E={xy1, xy2}E=\{xy_1,\ xy_2\}とすると、G=(X⊔Y,E)G=(X\sqcup Y,E)は頂点数33の有限単純二部グラフである。EEの二辺はともにxxを端点にもつので、二辺からなる辺集合はマッチングではなく、マッチングの辺数は11以下である。M={xy1}M=\{xy_1\}はマッチングであるから最大マッチングであり、ν(G)=1\nu(G)=1である。置き換えた定義では、MM-交互道v0,…,vkv_0,\dots,v_kでk≥1k\ge1であり一方の端点がMM-非飽和であるものをMM-増加道とよぶ。道y2,xy_2,xは長さ11のMM-交互道であり、端点y2y_2はMM-非飽和、もう一方の端点xxはMMに被覆される。「一方」をちょうど一方と読んでも少なくとも一方と読んでも、この道は置き換えた定義の意味のMM-増加道である。したがって、最大マッチングMMに対して置き換えた意味のMM-増加道が存在し、定理 1.5の同値は成り立たない。この道に沿って辺の所属を入れ替えると{xy1, xy2}\{xy_1,\ xy_2\}が得られ、xxが二本の辺に接するので、得られる辺集合はマッチングではない。

(3)を示す。まずZZの定義に現れる道の形を確かめる。この段は補題 3.1の証明の最初の段落と同じであり、MMの最大性を用いない。u∈Uu\in Uから出発し、長さが00であるか最初の辺がMMに属さないMM-交互道P: u=v0,v1,…,vkP:\ u=v_0,v_1,\dots,v_kをとる。交互性により、辺vi−1viv_{i-1}v_iがMMに属することとiiが偶数であることは同値である。u∈Xu\in Xであり各辺がXXとYYをまたぐので、vi∈Xv_i\in Xであることとiiが偶数であることは同値である。また、始点側の部分列v0,…,vjv_0,\dots,v_jも同じ条件を満たすMM-交互道であるから、PPに現れる頂点はすべてZZに属する。

CCが頂点被覆であることを示す。辺xy∈Exy\in E（x∈Xx\in X、y∈Yy\in Y）がx∉Cx\notin Cかつy∉Cy\notin Cを満たすと仮定すると、x∈Zx\in Zかつy∉Zy\notin Zである。xxへ至る上の形の道P: v0,…,vkP:\ v_0,\dots,v_kをとると、x∈Xx\in Xであるからkkは偶数である。xy∉Mxy\notin Mの場合、yyがPPに現れるならばy∈Zy\in Zである。yyがPPに現れないならば、列v0,…,vk,yv_0,\dots,v_k,yは道であり、k=0k=0のときは最初の辺xyxyがMMに属さず、k≥2k\ge2のときは最後の辺vk−1xv_{k-1}xがMMに属しxyxyが属さないので、この道はZZの定義の条件を満たしy∈Zy\in Zである。xy∈Mxy\in Mの場合、xxはMMに被覆されるのでx∉Ux\notin Uであり、k=0k=0ならばx=u∈Ux=u\in Uとなるのでk≥2k\ge2である。最後の辺vk−1xv_{k-1}xはMMに属し、MMはマッチングであるからvk−1x=xyv_{k-1}x=xy、すなわちvk−1=yv_{k-1}=yであり、yyはPPに現れるのでy∈Zy\in Zである。いずれの場合もy∉Zy\notin Zに反するので、CCは頂点被覆である。

MMが最大マッチングならばY∩ZY\cap ZがMM-非飽和頂点を含まないことを、対偶で示す。y∈Y∩Zy\in Y\cap ZがMM-非飽和であるとし、yyへ至る上の形の道P: v0,…,vkP:\ v_0,\dots,v_kをとる。y∈Yy\in Yであるからkkは奇数でありk≥1k\ge1である。始点v0∈Uv_0\in Uと終点yyはともにMM-非飽和であるから、PPはMM-増加道である。定理 1.5によりMMは最大マッチングでない。

逆に、Y∩ZY\cap ZがMM-非飽和頂点を含まないとする。x∈X∖Zx\in X\setminus ZがMM-非飽和ならばx∈Ux\in Uであり、長さ00の道によりx∈Zx\in Zとなって矛盾するので、CCの頂点はすべてMMに被覆される。CCの各頂点vvに、vvを被覆するただ一本のMMの辺φ(v)\varphi(v)を対応させる。φ(v)=φ(v′)=e\varphi(v)=\varphi(v')=eかつv≠v′v\ne v'と仮定すると、vvとv′v'はeeの二つの端点であり、一方xxがX∖ZX\setminus Zに、他方yyがY∩ZY\cap Zに属し、xy=e∈Mxy=e\in Mである。yyへ至る上の形の道P: v0,…,vkP:\ v_0,\dots,v_kをとると、kkは奇数であり最後の辺はMMに属さない。xxがPPに現れるならばx∈Zx\in Zである。xxがPPに現れないならば、列v0,…,vk,xv_0,\dots,v_k,xは道であり、最後の二辺の一方vk−1yv_{k-1}yがMMに属さず他方yxyxがMMに属するので、この道はZZの定義の条件を満たしx∈Zx\in Zである。いずれの場合もx∉Zx\notin Zに反するので、φ\varphiは単射であり∣C∣≤∣M∣\lvert C\rvert\le\lvert M\rvertである。CCは頂点被覆であるから、命題 2.2と合わせて

τ(G)≤∣C∣≤∣M∣≤ν(G)≤τ(G)\tau(G)\le\lvert C\rvert\le\lvert M\rvert\le\nu(G)\le\tau(G)

であり、∣M∣=ν(G)\lvert M\rvert=\nu(G)である。よってMMは最大マッチングである。

以上により、任意のマッチングMMについてCCは頂点被覆であり、Y∩ZY\cap ZにMM-非飽和頂点が見つかればそこへ至る道がMM-増加道を与え、見つからなければ∣C∣=∣M∣\lvert C\rvert=\lvert M\rvertがMMの最大性を確定させる。

(4)を示す。CCをGGの頂点被覆とする。各辺e∈Ee\in Eについて、eeの端点のうちCCに属するものを一つ選んでψ(e)∈C\psi(e)\in Cと定める。頂点v∈Cv\in Cについてψ(e)=v\psi(e)=vを満たす辺eeはvvに接するので、その本数はvvの次数以下、したがってΔ\Delta以下である。EEはψ\psiの各点の逆像に分割されるから∣E∣≤Δ∣C∣\lvert E\rvert\le\Delta\lvert C\rvertであり、∣C∣≥∣E∣/Δ\lvert C\rvert\ge\lvert E\rvert/\Deltaである。頂点数が最小の頂点被覆に用いるとτ(G)≥∣E∣/Δ\tau(G)\ge\lvert E\rvert/\Deltaであり、定理 3.2によりν(G)=τ(G)≥∣E∣/Δ\nu(G)=\tau(G)\ge\lvert E\rvert/\Deltaである。

次に、すべての頂点の次数が正の整数kkであるとする。各辺はXXの頂点をちょうど一つ端点にもつので、辺をXX側の端点によって分類すると∣E∣=k∣X∣\lvert E\rvert=k\lvert X\rvertであり、YY側の端点によって分類すると∣E∣=k∣Y∣\lvert E\rvert=k\lvert Y\rvertである。k≥1k\ge1であるから∣X∣=∣Y∣\lvert X\rvert=\lvert Y\rvertである。X=∅X=\emptysetならばY=∅Y=\emptysetであり、空なマッチングがすべての頂点を被覆する。X≠∅X\ne\emptysetならばΔ=k\Delta=kであり、前段によりν(G)≥k∣X∣/k=∣X∣\nu(G)\ge k\lvert X\rvert/k=\lvert X\rvertである。最大マッチングMMをとると∣M∣≥∣X∣\lvert M\rvert\ge\lvert X\rvertである。MMの各辺はXXの頂点をちょうど一つ端点にもち、MMの相異なる二辺は端点を共有しないから、MMの辺にXX側の端点を対応させる写像は単射である。よって∣M∣≤∣X∣\lvert M\rvert\le\lvert X\rvertであり、∣M∣=∣X∣\lvert M\rvert=\lvert X\rvertとなって、この写像は全単射である。すなわちMMはXXのすべての頂点を被覆する。同じ議論により、YY側の端点を対応させる写像も単射であり∣M∣=∣Y∣\lvert M\rvert=\lvert Y\rvertであるから、MMはYYのすべての頂点も被覆する。

(5)を示す。添字は2m+12m+1を法として読み、GmG_mの辺をcici+1c_ic_{i+1}（0≤i≤2m0\le i\le2m）と書く。m≥1m\ge1であるから頂点は33個以上あり、GmG_mの各頂点の次数は22である。

ν(Gm)=m\nu(G_m)=mを示す。マッチングMMの相異なる二辺は端点を共有しないので、MMの辺の端点は全部で2∣M∣2\lvert M\rvert個の相異なる頂点であり、2∣M∣≤2m+12\lvert M\rvert\le2m+1である。∣M∣\lvert M\rvertは整数であるから∣M∣≤m\lvert M\rvert\le mである。一方、{c0c1, c2c3, …, c2m−2c2m−1}\{c_0c_1,\ c_2c_3,\ \dots,\ c_{2m-2}c_{2m-1}\}は端点がすべて相異なるmm本の辺からなるのでマッチングである。よってν(Gm)=m\nu(G_m)=mである。

τ(Gm)=m+1\tau(G_m)=m+1を示す。頂点被覆CCをとり、各辺eeに、eeの端点のうちCCに属するものを一つ選んで対応させる。各頂点に対応する辺はその頂点に接するので22本以下であり、辺は2m+12m+1本あるから2m+1≤2∣C∣2m+1\le2\lvert C\rvertである。∣C∣\lvert C\rvertは整数であるから∣C∣≥m+1\lvert C\rvert\ge m+1である。一方、C0={c0,c2,…,c2m}C_0=\{c_0,c_2,\dots,c_{2m}\}はm+1m+1個の頂点からなる。0≤i≤2m−10\le i\le2m-1のとき辺cici+1c_ic_{i+1}の端点の添字iiとi+1i+1の一方は2m2m以下の偶数であり、辺c2mc0c_{2m}c_0はc0c_0を端点にもつので、C0C_0は頂点被覆である。よってτ(Gm)=m+1\tau(G_m)=m+1である。

任意の有限単純グラフGGについて不等式を示す。ν(G)≤τ(G)\nu(G)\le\tau(G)は、命題 2.2の証明が二部性を用いないことによる。実際、マッチングMMと頂点被覆CCについて、MMの各辺にCCに属する端点を一つ対応させる写像は、MMの相異なる二辺が端点を共有しないので単射であり、∣M∣≤∣C∣\lvert M\rvert\le\lvert C\rvertである。τ(G)≤2ν(G)\tau(G)\le2\nu(G)を示す。最大マッチングMMをとり、MMの辺の端点全体をCCとすると∣C∣=2∣M∣\lvert C\rvert=2\lvert M\rvertである。どちらの端点もCCに属さない辺eeが存在すると仮定すると、eeはMMのどの辺とも端点を共有しないのでM∪{e}M\cup\{e\}はマッチングであり、e∉Me\notin Mであるから∣M∪{e}∣=∣M∣+1\lvert M\cup\{e\}\rvert=\lvert M\rvert+1となってMMの最大性に反する。よってCCは頂点被覆であり、τ(G)≤∣C∣=2ν(G)\tau(G)\le\lvert C\rvert=2\nu(G)である。

m=1m=1のときG1G_1は長さ33の閉路であり、ν(G1)=1\nu(G_1)=1、τ(G1)=2=2ν(G1)\tau(G_1)=2=2\nu(G_1)であるから、右側の不等式は等号で成り立つ。m≥1m\ge1のすべてでν(Gm)<τ(Gm)\nu(G_m)<\tau(G_m)であるから、定理 3.2の結論は二部でないグラフでは成り立たない場合がある。▨

注意 5.2. 二部でないグラフの最大マッチング、重み付きマッチングおよび完全マッチングの存在条件は、本記事では扱っていない。

参考文献

  1. Reinhard Diestel, Graph Theory, 6th ed., Graduate Texts in Mathematics 173, Springer, Berlin, 2025.二部グラフのマッチングと Kőnig の定理の定式化を参考にした。
  2. J. A. Bondy and U. S. R. Murty, Graph Theory, Graduate Texts in Mathematics 244, Springer, London, 2008.交互道と増加道による最大マッチングの特徴づけ、および対称差による証明を参考にした。
  3. Alexander Schrijver, Combinatorial Optimization: Polyhedra and Efficiency, Algorithms and Combinatorics 24, vol. A, Springer, 2003.増加道を繰り返し探す手続きと、交互到達集合から頂点被覆を構成する議論を参考にした。

前提記事