有限幾何学　 　　　　　　第12回.

Presentation on theme: "　　　　有限幾何学　 　　　　　　第12回."— Presentation transcript:

1 　　　　有限幾何学　 　　　　　　第12回

2 有限幾何学　第12回 マッチング 用語の説明 最大マッチング 2部グラフのマッチング

3 1.1 用語の説明 グラフGの辺部分集合M⊆E(G)に対して， Mの任意の2辺が共通の端点を持たないとき， MをGのマッチングという．
1.1　用語の説明 グラフGの辺部分集合M⊆E(G)に対して， Mの任意の2辺が共通の端点を持たないとき， MをGのマッチングという． グラフGの辺数最大のマッチングを Gの最大マッチングという． 　　　　　　　　　　　　　　　　　　　　　　例：赤の辺集合はこのグラフの最大マッチング

4 1.1 用語の説明 グラフGの頂点ｖが， GのマッチングMに属するある辺の端点であるとき， ｖはMによって飽和されているという．
1.1　用語の説明 グラフGの頂点ｖが， GのマッチングMに属するある辺の端点であるとき， ｖはMによって飽和されているという． グラフGの全ての頂点を飽和しているマッチングを， Gの完全マッチングあるいは1因子という． 　　　　　　　　　　　　　　　　　　　　　　　　　　　　　例：赤の辺集合はこのグラフの完全マッチング

5 1.2 最大マッチング グラフの辺集合をいくつかの最大マッチングに分解する という研究が行われている．
1.2　最大マッチング グラフの辺集合をいくつかの最大マッチングに分解する という研究が行われている． 完全グラフに関しては次の定理が簡単に分かる． 定理1 (1) K2nの辺集合は2n-1個の完全マッチングに分解できる． (2) K2n-1の辺集合は2n-1個の最大マッチングに分解できる．

6 1.2　最大マッチング 定理1 (1) K2nの辺集合は2n-1個の完全マッチングに分解できる （1）の例（K6）：

7 1.2　最大マッチング 次に，与えられたマッチングを修正する方法と， マッチングが最大マッチングであるための必要十分条件の紹介をする．

8 1.2 最大マッチング M-交互道：Mに属する辺と属さない辺が交互に並ぶ道 M-増大道：始点と終点がMによって飽和されていないM-交互道
1.2　最大マッチング M-交互道：Mに属する辺と属さない辺が交互に並ぶ道 M-増大道：始点と終点がMによって飽和されていないM-交互道 　　　　　　　　　　　　　　　　　　　例：青の道は増大道　　　

9 1.2　最大マッチング M-増大道上のマッチングの辺を入れ替えることにより， マッチングの修正を行うことができる． 　　　　　　　　　　　　　　　　　　　　⇒

10 1.2 最大マッチング 最大マッチングと最大道の間には次のような関係がある． 定理2 M：グラフGのマッチング
1.2　最大マッチング 最大マッチングと最大道の間には次のような関係がある． 定理2 M：グラフGのマッチング Mが最大マッチングである⇔GがM-増大道を含まない

11 1.2 最大マッチング 最大マッチングと最大道の間には次のような関係がある． 定理2 M：グラフGのマッチング
1.2　最大マッチング 最大マッチングと最大道の間には次のような関係がある． 　注意：⇒が成立することは明らか　　　　　　　　　　　　　　　　　 定理2 M：グラフGのマッチング Mが最大マッチングである⇔GがM-増大道を含まない

12 1.2 最大マッチング 定理2 M：グラフGのマッチング Mが最大マッチングである⇔GがM-増大道を含まない ⇐の証明：
1.2　最大マッチング ⇐の証明： MをグラフGのマッチングとし，GがM-増大道を含まないと仮定する． このとき，Mが最大マッチングではないと仮定し，矛盾を導く． M’：最大マッチング M△M’ ：MまたはM’どちらか片方だけに属する辺からなる集合 　　　　　（MとM’の差集合） 定理2 M：グラフGのマッチング Mが最大マッチングである⇔GがM-増大道を含まない

13 1.2 最大マッチング 定理2 M：グラフGのマッチング Mが最大マッチングである⇔GがM-増大道を含まない ⇐の証明：
1.2　最大マッチング ⇐の証明： MとM’はマッチングなので Mの辺から構成されるグラフの最大次数は高々1， M’の辺から構成されるグラフの最大次数も高々1． よって，M△M’ の辺から誘導される誘導部分グラフG’は 最大次数が2以下となる． 定理2 M：グラフGのマッチング Mが最大マッチングである⇔GがM-増大道を含まない

14 1.2 最大マッチング 定理2 M：グラフGのマッチング Mが最大マッチングである⇔GがM-増大道を含まない ⇐の証明：
1.2　最大マッチング ⇐の証明： G’は最大次数が2以下なので， 互いに共有点を持たないいくつかの閉路と道に分割することができる． 　　　　　　　　注意：差集合を取ってきたのでMとM’の辺が交互に並ぶ． 定理2 M：グラフGのマッチング Mが最大マッチングである⇔GがM-増大道を含まない 赤はM’の辺 青はMの辺

15 1.2 最大マッチング 定理2 M：グラフGのマッチング Mが最大マッチングである⇔GがM-増大道を含まない ⇐の証明：
1.2　最大マッチング ⇐の証明： |M’|>|M|より，少なくとも1つの道がM-増大道となり，矛盾． よって， Mは最大マッチングである．　 定理2 M：グラフGのマッチング Mが最大マッチングである⇔GがM-増大道を含まない 赤はM’の辺 青はMの辺

16 1.2 最大マッチング 次にマッチングと辺彩色の関係を紹介する． 辺彩色： 隣接する辺が異なる色となるようなグラフの辺全体への色の塗り方
1.2　最大マッチング 次にマッチングと辺彩色の関係を紹介する． 辺彩色： 隣接する辺が異なる色となるようなグラフの辺全体への色の塗り方 辺彩色に関して，次の定理が有名（Δ(G)はGの最大次数）　 定理3（Vizingの定理） グラフGの辺集合はΔ(G)またはΔ(G)+1の色で辺彩色可能である

17 1.2 最大マッチング グラフを辺彩色したとき，同色の辺集合は そのグラフのマッチングとみなすこともできる．
1.2　最大マッチング グラフを辺彩色したとき，同色の辺集合は そのグラフのマッチングとみなすこともできる． このことから，Vizingの定理は次のように 言い換えることができる．　　　　　　　　　　　　　　　　　　　　　　　　　　　　　 定理4（Vizingの定理の言い換え） グラフGの辺集合はΔ(G)またはΔ(G)+1個のマッチングに分解できる 定理3（Vizingの定理） グラフGの辺集合はΔ(G)またはΔ(G)+1の色で辺彩色可能である

18 1.3 2部グラフのマッチング ２部グラフのマッチングの例として次の問題を考える． 男性のグループがあり，各男性は何人かの女性と知り合いで
1.3　2部グラフのマッチング ２部グラフのマッチングの例として次の問題を考える． 男性のグループがあり，各男性は何人かの女性と知り合いで あるとする．全ての男性が知り合いの女性と結婚できるように， カップルが組めるにはどんな条件が必要か？ 男性 男性と知り合いの女性 東方 椎名，牧瀬，桐生 虹村 漆原 岸部 阿万音，比屋定，牧瀬 空条 阿万音，牧瀬

19 1.3 2部グラフのマッチング 男性の集合をV1, 女性の集合をV2とすると，
1.3　2部グラフのマッチング 男性の集合をV1, 女性の集合をV2とすると， この問題は，「2部グラフG(V1,V2)にV1の全ての頂点を飽和する マッチングがあるかどうか」という問題に 置き換えて考えることができる． 　　　　　　　　　　　 V V2 東方 虹村 岸部 空条 椎名 牧瀬 桐生 漆原 阿万音 比屋定 ｖ

20 1.3 2部グラフのマッチング この問題に関して，次の必要十分条件が知られている． 定理5（Hallの結婚定理）
1.3　2部グラフのマッチング この問題に関して，次の必要十分条件が知られている． 注意：NG(A)=∪v∊ANG(v) 定理5（Hallの結婚定理） G=G(V1,V2)：部集合がV1とV2の2部グラフ V1の頂点を全て飽和するマッチングが存在する ⇔ V1の任意の部分集合Aに対して，|NG(A)|≧|A|

21 1.3 2部グラフのマッチング Hallの結婚定理の証明： （⇒の証明） V1からV2への
1.3　2部グラフのマッチング Hallの結婚定理の証明： （⇒の証明） V1からV2への 完全マッチングMによって誘導される誘導部分グラフをG’とすると， V1の任意の部分集合Aに対して，|A|=|NG’(A)|≦|NG(A)| ｖ A NG(A) V1 V2 NG’(A)

22 1.3 2部グラフのマッチング Hallの結婚定理の証明：（⇐の証明） V1={ v1,v2,…, vn}とおく．
1.3　2部グラフのマッチング Hallの結婚定理の証明：（⇐の証明） V1={ v1,v2,…, vn}とおく． nに関する帰納法で証明する．（ n=1のときは明らか ） V1の真部分集合Aに対して， |NG(A)|=|A|であるとき，Aを臨界集合と呼ぶ． 臨界集合が存在するか，存在しないかに分けて証明する．

23 1.3 2部グラフのマッチング Hallの結婚定理の証明：（⇐の証明） 場合1：臨界集合が存在しない場合
1.3　2部グラフのマッチング Hallの結婚定理の証明：（⇐の証明） 場合1：臨界集合が存在しない場合 x∊NG(vn)を選ぶ（どれでもよい）． G’をGからvnとxを取り除いた結果生じるグラフとする． このとき，臨界集合が存在しないことから， V1-{vn}の任意の部分集合Aに対して， |NG’(A)|≧ |NG(A)|-|{x}|≧|A|+1-|{x}|=|A| よってG’に対して帰納法の仮定を適用することで V1-{vn}からV2-{x}への完全マッチングMが存在することが分かる． このとき，M∪{xvn}がV1の全ての頂点を飽和するマッチングとなる．

24 1.3 2部グラフのマッチング Hallの結婚定理の証明：（⇐の証明） 場合2：臨界集合が存在する場合
1.3　2部グラフのマッチング Hallの結婚定理の証明：（⇐の証明） 場合2：臨界集合が存在する場合 V1’={v1, v2,…, vl}を臨界集合としてよい（注：l < n）． V2’=NG(V1’)とおき， G’を V1’∪V2’ によって誘導される誘導部分グラフとする． 注：V1’は臨界集合なので|V2’|=|NG(V1’)|=|V1’| このとき， V1’の任意の部分集合Aに対して，|NG’(A)|=|NG(A)|≧|A| よってG’に対して帰納法の仮定を適用することで V1’の全ての頂点を飽和するマッチングM1 が存在することが分かる．

25 1.3 2部グラフのマッチング Hallの結婚定理の証明：（⇐の証明） 場合2：臨界集合が存在する場合
1.3　2部グラフのマッチング Hallの結婚定理の証明：（⇐の証明） 場合2：臨界集合が存在する場合 V1’’= V1-V1’ , V2’’= V2-V2’ とする． G’’を V1’’∪V2’’ によって誘導される誘導部分グラフとする． このとき，V1’’の任意の部分集合Aに対して， |NG’’(A)|=|NG(A∪V1’)|-|V2’| ≧(|A∪V1’|) -|V2’|=(|A|+|V1’|)-|V2’|=|A| よってG’’に対して帰納法の仮定を適用することで V1’’の全ての頂点を飽和するマッチングM2 が存在することが分かる． M1∪M2がV1の全ての頂点を飽和するマッチングとなる．

26 1.3 2部グラフのマッチング Hallの結婚定理を用いて次の定理を証明することができる． 定理6 定理6の証明：
1.3　2部グラフのマッチング Hallの結婚定理を用いて次の定理を証明することができる． 定理6の証明： G(V1,V2)をk-正則2部グラフとする． 証明は次の2つのパートから構成されている |V1|=|V2| V1の頂点を全て飽和するマッチングが存在する 注意：①より，②のマッチングが完全マッチングであることが分かる 定理6 正則2部グラフには完全マッチングが存在する．

27 1.3 2部グラフのマッチング Hallの結婚定理を用いて次の定理を証明することができる． 定理6 |V1|=|V2| の証明：
1.3　2部グラフのマッチング Hallの結婚定理を用いて次の定理を証明することができる． |V1|=|V2|　の証明： |E(G)|=∑v∊V1dG(v)=k|V1| |E(G)|=∑v∊V2dG(v)=k|V2| より分かる 定理6 正則2部グラフには完全マッチングが存在する．

28 1.3 2部グラフのマッチング Hallの結婚定理を用いて次の定理を証明することができる． 定理6
1.3　2部グラフのマッチング Hallの結婚定理を用いて次の定理を証明することができる． V1の頂点を全て飽和するマッチングが存在する　の証明： SをV1の任意の部分集合とする． Sの頂点に隣接する辺はNG(S)のある頂点に隣接するので， Sに隣接する辺の総数≦NG(S)に隣接する辺の総数 ∴k|S|≦k|NG(S)|つまり，|S|≦|NG(S)| SはV1の任意の部分集合であったので， Hallの結婚定理から②が分かる． 定理6 正則2部グラフには完全マッチングが存在する．

29 1.3 2部グラフのマッチング 正則2部グラフから完全マッチングを除いたグラフも 正則2部グラフであることから，
1.3　2部グラフのマッチング 正則2部グラフから完全マッチングを除いたグラフも 正則2部グラフであることから， 定理6より，次の定理が成り立つことが簡単に分かる． 定理7 正則2部グラフの辺集合は完全マッチングに分割できる． 定理6 正則2部グラフには完全マッチングが存在する．

30 提出課題12 問1：K5の辺集合を5個の最大マッチングに分解せよ． 問2：Δ(G)個のマッチングに辺集合が分割できないK3以外の
　　 グラフの例を1つ挙げよ． 問3（ハーレム問題）： Bは男性の集合とし，Bの各男性は2人以上の 恋人と結婚したいとする． この問題に解があるための必要十分条件を見つけよ．

31 提出課題12 問3のヒント： 2部グラフG(V1,V2)に置き換えて考える．（V1が男性の集合）
x∊V1, y,z∊V2 xy,xz∊E(G(V1,V2))の形のG(V1,V2)の部分グラフ全体からなる集合をS(G)とおく． 問３は，次の集合M⊆S(G)が存在するための必要十分条件を求める問題に置き換えることができる． ∀X,∀Y∊M, X∩Y=∅　かつ　∀x∊V1 ∃X∊M s.t. x∊V(X)　

32 提出課題12 問3のヒント： 問３は，次の集合M⊆S(G)が存在するための必要十分条件を求める問題に置き換えることができる． ∀X,∀Y∊M, X∩Y=∅　かつ　∀x∊V1 ∃X∊M s.t. x∊V(X)　 「∃M ⊆S(G) s.t. （∀X,∀Y∊M, X∩Y=∅　かつ　∀v∊V1 ∃X∊M s.t. v∊V(X)）」 ⇒ 「V1の任意の部分集合Aに対して，|NG(A)|≧2|A|」 は簡単に分かる． （Hallの結婚定理の⇒の証明とほぼ同じ）

33 提出課題12 ⇒ 問3のヒント：⇐の証明のヒント まずは，V1の各頂点を2個の独立点に分ける． G G’ u' u u v v v' V1

34 提出課題12 問3のヒント：⇐の証明のヒント G’においてV1’の頂点を全て飽和するマッチングが存在すると， G G’ u' u u v v

35 提出課題12 ⇐ 問3のヒント：⇐の証明のヒント Gにおいて所望のMが存在することが分かる． G G’ u' u u v v v' V1

36 提出課題12 問3のヒント： G’においてV1’の頂点を全て飽和するマッチングが存在する ことを示せばよい． ホールの結婚定理を用いて示してみましょう．