グラフ理論による証明とは? わかりやすく解説

Weblio 辞書 > 辞書・百科事典 > ウィキペディア小見出し辞書 > グラフ理論による証明の意味・解説 

グラフ理論による証明

出典: フリー百科事典『ウィキペディア(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 となり、矛盾

※この「グラフ理論による証明」の解説は、「ホールの定理」の解説の一部です。
「グラフ理論による証明」を含む「ホールの定理」の記事については、「ホールの定理」の概要を参照ください。

ウィキペディア小見出し辞書の「グラフ理論による証明」の項目はプログラムで機械的に意味や本文を生成しているため、不適切な項目が含まれていることもあります。ご了承くださいませ。 お問い合わせ



英和和英テキスト翻訳>> Weblio翻訳
英語⇒日本語日本語⇒英語
  

辞書ショートカット

すべての辞書の索引

「グラフ理論による証明」の関連用語

グラフ理論による証明のお隣キーワード
検索ランキング

   

英語⇒日本語
日本語⇒英語
   



グラフ理論による証明のページの著作権
Weblio 辞書 情報提供元は 参加元一覧 にて確認できます。

   
ウィキペディアウィキペディア
Text is available under GNU Free Documentation License (GFDL).
Weblio辞書に掲載されている「ウィキペディア小見出し辞書」の記事は、Wikipediaのホールの定理 (改訂履歴)の記事を複製、再配布したものにあたり、GNU Free Documentation Licenseというライセンスの下で提供されています。

©2025 GRAS Group, Inc.RSS