グラフ理論による証明
出典: フリー百科事典『ウィキペディア（Wikipedia）』 (2020/01/14 20:57 UTC 版)
「ホールの定理」の記事における「グラフ理論による証明」の解説
まず、2部グラフ G = (X + Y, E ) = G(X, Y ) が X-飽和マッチング（X の全ての頂点を飽和するようなマッチング）を持つならば、任意のW ⊆ X に対して|NG(W )| ≥ |W |であることを示す。 MをX-飽和マッチングとする。このとき、Mによって、与えられたW ⊆ X とマッチングされているY の頂点集合をM(W )と書くと、マッチングの定義より|M(W )|=|W |。しかし、M(W )の全ての元はW の近傍に属するので、M(W ) ⊆ NG(W )である。よって、 |NG(W )| ≥ |M(W )| であるから、|NG(W)| ≥ |W |。 次に、任意のW ⊆ X に対して|NG(W)| ≥ |W | ならば、G(X,Y)はX-飽和マッチングを持つことを示す。 2部グラフG(X,Y)がX-飽和マッチングを持たないと仮定して矛盾を導く。M をGの最大マッチングすると、M-非飽和点が存在するので、これをu ∈ X とする。u を始点とする任意のM-交互道を考え、この交互道によってuと接続するすべてのY の頂点の集合をT とする。同様に、uと接続するすべてのX の頂点の集合(u 自身も含む)をW とする。u を始点とするM-交互道の終点が、Yに属する点となること（つまり、M-増大道となること）はない。（もしそのようなことがあれば、M より真に大きなマッチングが構成でき、M の最大性に矛盾する。）ここで、T に属する全ての頂点は、MによりW の頂点とマッチングされており、逆に全ての頂点 v ∈ W \ {u} はMによりT の頂点とマッチングされているので、M は W \ {u} と T の間の全単射を与える。よって、 |W | = |T | + 1であり、NG(W) ⊇ T が成立する。他方、v ∈ Y をw ∈ W に接続される頂点としたとき、辺 (w,v ) が Mに属していれば、v ∈ T。そうでなければ、辺 (w,v ) を通るM-交互道を構成できるので、v ∈ Tとなり、NG(W) ⊆ Tが成立。したがって、 |NG(W)| = |T | = |W | − 1 となり、矛盾。
※この「グラフ理論による証明」の解説は、「ホールの定理」の解説の一部です。
「グラフ理論による証明」を含む「ホールの定理」の記事については、「ホールの定理」の概要を参照ください。
- グラフ理論による証明のページへのリンク
