グラフ理論・組み合わせ論第1回レポートについて

グラフ理論・組み合わせ論
第１回レポートについて
情報学部門瀧本英二
http://www.i.kyushu-u.ac.jp/~eiji
2
レポート
1. Hall の結婚定理の必要性の証明を与えよ．
【必要性】
２部グラフ (𝐴∪𝐵,𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, |𝑁(𝑆)| ≥ |𝑆|．
2. ２部グラフの任意の最大マッチング𝑀に対し，
𝑀 に関する増大道が存在しないことを示せ．
3
１． Hall の結婚定理の必要性の証明を与えよ．
【必要性】
２部グラフ (𝐴∪𝐵,𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, |𝑁(𝑆)| ≥ |𝑆|．
残念ながら，多くのレポートの証明は不完全
もしくは論理展開に誤りがあった．
いくつか事例を見ていきましょう．
4
事例１
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, |𝑁(𝑆)| ≥ |𝑆|．
∀𝑆 ⊆ 𝐴, |𝑁(𝑆)| ≥ |𝑆| が成立しない時ある 𝑆 の部分集合 𝐴 が
存在して， ∀𝑆 ⊆ 𝐴, 𝑁 𝑆 < |𝑆| となる．
よって 𝐴 をカバーするようなマッチングは存在せず，
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が 𝐴 のマッチングを持つという条件は
成り立たない．よって，対偶が証明されたため必要性は示された．
同様のレポート多数！
5
事例１
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, |𝑁(𝑆)| ≥ |𝑆|．
𝑆
𝐴 ある
∀𝑆 ⊆ 𝐴, |𝑁(𝑆)| ≥ |𝑆| が成立しない時ある 𝑆 の部分集合 𝐴 が
存在して， ∀𝑆 ⊆ 𝐴, 𝑁 𝑆 < |𝑆| となる．
よって 𝐴 をカバーするようなマッチングは存在せず，
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が 𝐴 のマッチングを持つという条件は
成り立たない．よって，対偶が証明されたため必要性は示された．
もっとも肝心な部分．
「対偶が成り立つのは明らかなので，必要性が示された」
と言っていることと同じで，レポートの趣旨に反する．
6
事例２
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, |𝑁(𝑆)| ≥ |𝑆|．
|𝑁(𝑆)| < |𝑆| と仮定すると，鳩の巣原理より，𝐵 の同じ頂点に
接続する 𝐴 の頂点が存在する．これは２部グラフが 𝐴 の全ての
頂点に接続するマッチングを持つことに矛盾する．
7
事例２
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, |𝑁(𝑆)| ≥ |𝑆|．
∃𝑆 ⊆ 𝐴
|𝑁(𝑆)| < |𝑆| と仮定すると，鳩の巣原理より，𝐵 の同じ頂点に
接続する 𝐴 の頂点が存在する．これは２部グラフが 𝐴 の全ての
頂点に接続するマッチングを持つことに矛盾する．
鳩の巣原理をどこに適用したのか不明．また，
「𝐵 の同じ頂点に接続する 𝐴 の複数の頂点」
の意味としても，そのような辺が２部グラフに存在したからと
いって，矛盾を導けない．
8
事例２
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, |𝑁(𝑆)| ≥ |𝑆|．
∃𝑆 ⊆ 𝐴
|𝑁(𝑆)| < |𝑆| と仮定すると，鳩の巣原理より，𝐵 の同じ頂点に
接続する 𝐴 の頂点が存在する．これは２部グラフが 𝐴 の全ての
頂点に接続するマッチングを持つことに矛盾する．
おそらく，任意の関数 𝑓: 𝐴 → 𝐵 （ただし， (𝑎, 𝑓(𝑎) ∣ 𝑎 ∈ 𝐴 ⊆ 𝐸）
が単射（１対１対応）ではないことを示そうとしていると思われる．
𝑓 の 𝑆 への制限
𝑓𝑆 : 𝑆 → 𝑁 𝑆 𝑓𝑆 𝑎 = 𝑓 𝑎 , ∀𝑎 ∈ 𝑆
が鳩の巣原理により単射ではないので．
9
事例３
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ．
2部グラフ (𝐴 ∪ 𝐵, 𝐸) が 𝐴 のマッチングを持っているとする．
マッチングによって 𝑆 ⊆ 𝐴 とマッチングしている 𝐵 の頂点 𝑡 は
𝑆 = 𝑡
である．このとき 𝑁 𝑆 ≥ 𝑡 であるので
𝑁 𝑆 ≥ 𝑆．
10
事例３
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ．
𝑀⊆𝐸
つ
2部グラフ (𝐴 ∪ 𝐵, 𝐸) が 𝐴 のマッチングを持っているとする．
マッチングによって 𝑆 ⊆ 𝐴 とマッチングしている 𝐵 の頂点 𝑡 は
𝑆 = 𝑡
を満たす．
集合
である．このとき 𝑁 𝑆 ≥ 𝑡 であるので
（𝑡 は大文字
の方がよい）
一方，𝑡 ⊆ 𝑁(𝑆) より 𝑁 𝑆 ≥ 𝑆 ．
任意の 𝑆 ⊆ 𝐴 に対し，𝑀
11
事例４
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ．
𝐴 のすべての頂点に接続するマッチングを 𝑀 ⊆ 𝐸 とする．
𝐴 の部分集合 𝑇 について，
𝑁 ′ 𝑇 = 𝑣 ∈ 𝐵 ∃𝑢 ∈ 𝑆, 𝑢, 𝑣 ∈ 𝑀
とする．このとき，任意の 𝑆 ⊆ 𝐴 について，𝑁 𝑆 ⊇ 𝑁′(𝑆)．
よって，
𝑁 𝑆 ≥ 𝑁′ 𝑆 = 𝑆 ．
12
事例４
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ．
𝐴 のすべての頂点に接続するマッチングを 𝑀 ⊆ 𝐸 とする．
𝐴 の部分集合 𝑇 について，
𝑇
′
𝑁 𝑇 = 𝑣 ∈ 𝐵 ∃𝑢 ∈ 𝑆, 𝑢, 𝑣 ∈ 𝑀
とする．このとき，任意の 𝑆 ⊆ 𝐴 について，𝑁 𝑆 ⊇ 𝑁′(𝑆)．
よって，
𝑁 𝑆 ≥ 𝑁′ 𝑆 = 𝑆 ．
おしい．𝑁 ′ 𝑇 より 𝑁𝑀 𝑇 の方がよさそう．𝑇 ではなく 𝑆 としても
問題ない．また，「マッチングの定義より，任意の 𝑇 ⊆ 𝐴 に対し，
𝑁𝑀 𝑇 = 𝑇 に注意．」のような一文があると，親切．
13
事例５
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ．
𝐴 がマッチングを持つので，頂点 𝑎 ∈ 𝐴 に対し，辺で繋がって
いる頂点 𝑏 ∈ 𝐵 が少なくとも1つ存在する．従って，
∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ．
14
事例５
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ．
任意の
𝑎 と隣接して
𝐴 がマッチングを持つので，頂点 𝑎 ∈ 𝐴 に対し，辺で繋がって
いる頂点 𝑏 ∈ 𝐵 が少なくとも1つ存在する．従って，
∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ．
不十分．各頂点 𝑎 ∈ 𝐴 に対し，相異なる頂点 𝑏 ∈ 𝐵 が存在
ことを示す必要がある．
15
事例６
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ．
対偶を示す．
∀𝑆 ⊆ 𝐴, 𝑁 𝑆 < 𝑆 が成り立つとする．
ここで，𝑆 が 𝑠 という集合だと考えると，𝑁(𝑆)は空集合となる．
この場合，𝐴 のマッチングは存在しない．
16
事例６
【証明したいこと】
２部グラフ (𝐴 ∪ 𝐵, 𝐸) が，𝐴 のマッチングを持つ
⇒ ∀𝑆 ⊆ 𝐴, 𝑁 𝑆 ≥ 𝑆 ．
∃ 対偶を示す．
∀𝑆 ⊆ 𝐴, 𝑁 𝑆 < 𝑆 が成り立つとする．
ここで，𝑆 が 𝑠 という集合だと考えると，𝑁 𝑆 は空集合となる．
この場合，𝐴 のマッチングは存在しない．
𝑆 は任意に選べないので， 𝑆 = 1 と仮定できない．
17
２．２部グラフの任意の最大マッチング 𝑀 に
対し，𝑀 に関する増大道が存在しない
ことを示せ．
𝑎
𝐴
𝐵
𝑏
𝑀 に関する増大道
• 𝐴 のある頂点 𝑎 から 𝐵 のある頂点 𝑏 への道．
• 𝐸 − 𝑀 の辺（黒い辺）と 𝑀 の辺（赤い辺）を
交互に通る．
• 𝑎 と 𝑏 に接続する 𝑀 の辺は存在しない．
18
事例７
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
𝐴
𝐵
真の最大マッチングを 𝑀′とする．
𝑀 と 𝑀′のちょうど片方に属している枝の集合を 𝑀Δ𝑀′ とする．
マッチングの性質より，一つの頂点に隣接している 𝑀Δ𝑀′ の枝は
二本以下なので， 𝑀Δ𝑀′ はサイクルとパスに分解できる．
サイクルについて：𝑀 の枝と 𝑀′ が交互に登場．
パスについて：𝑀′の枝からはじまり𝑀′の枝で終わるパスが存在．
このパスこそが 𝑀 の増加道である．
19
事例７
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
𝐴
𝐵
真の最大マッチングを 𝑀′とする．
𝑀 と 𝑀′のちょうど片方に属している枝の集合を 𝑀Δ𝑀′ とする．
マッチングの性質より，一つの頂点に隣接している 𝑀Δ𝑀′ の枝は
二本以下なので， 𝑀Δ𝑀′ はサイクルとパスに分解できる．
サイクルについて：𝑀 の枝と 𝑀′ が交互に登場．
パスについて：𝑀′の枝からはじまり𝑀′の枝で終わるパスが存在．
このパスこそが 𝑀 の増加道である．
「𝑀 が最大マッチングでないならば，𝑀 に関する増大道が存在」
を証明しようとしているようにみえる．（不十分だが．）
20
事例８
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
𝐴
マッチング 𝑀 に対して増大道 𝑚 を持つとする．
𝑀Δ𝑚 はマッチングであり，𝑀Δ𝑚 = |𝑀| + 1 となり
𝑀 は最大ではないことになり，つまりマッチング 𝑀 に対して
増大道は存在しないことが示された．
同様のレポート多数！
𝐵
21
事例８
𝐴
𝐵
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
関する
が存在する
マッチング 𝑀 に対して増大道 𝑚 を持つとする．
𝑀Δ𝑚 はマッチングであり， 𝑀Δ𝑚 = |𝑀| + 1 となりとなるので，
𝑀 は最大ではないことになり，つまりマッチング 𝑀 に対して関する
増大道は存在しないことが示された．．よって，最大
マッチング
この部分を，増大道の条件を用いて証明したい．
※増大道が辺の集合として定義されていることを明記する
必要がある．
22
事例９
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
𝐴
𝐵
増大道が存在すると仮定する．
増大道にはマッチしていない 𝐴 の頂点と 𝐵 の頂点が存在する．
この２つの頂点を結ぶことでさらにマッチングを増やすことができ
るので，これは最大マッチングではない．
23
事例９
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
𝐴
𝐵
増大道が存在すると仮定する．
増大道にはマッチしていない 𝐴 の頂点と 𝐵 の頂点が存在する．
この２つの頂点を結ぶことでさらにマッチングを増やすことができ
るので，これは最大マッチングではない．
この２頂点間に辺があるとは限らない．
24
事例１０
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
𝐴
任意のマッチング 𝑀′ ⊆ 𝐸 に対し，増大道が存在
するとき， 𝑀′ よりも 𝐸 − 𝑀′ の方が大きく，𝐸 − 𝑀′の方が
マッチ数の多いマッチングとなる．
この時最大マッチング 𝑀 に対し，𝑀 よりもマッチ数の多い
マッチングは存在しないため，増大道は存在しない．
𝐵
25
事例１０
𝐴
𝐵
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
関する
任意のマッチング 𝑀′ ⊆ 𝐸 に対し，増大道が存在
するとき， 𝑀′ よりも 𝐸 − 𝑀′ の方が大きく，𝐸 − 𝑀′の方が
マッチ数の多いマッチングとなる．
この時最大マッチング 𝑀 に対し，𝑀 よりもマッチ数の多い
マッチングは存在しないため，増大道は存在しない．
よって，𝑀′ は最大マッチングではない．
増大道を構成する辺の集合 𝑚 に制限した議論をしている
ようにみえる．つまり， 𝑀′ ∩ 𝑚 < 𝐸 − 𝑀′ ∩ 𝑚 ，かつ
𝐸 − 𝑀′ ∩ 𝑚 はマッチング（これは正しい）．しかし，𝑀′ − 𝑚
の辺を加えたマッチング同士で比較する必要がある．
26
事例１１
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
𝐴
𝐵
対偶を示す．対偶は，
マッチング𝑀に関する増大道が存在すれば，𝑀 は最大マッチング．
𝑎1 , 𝑎2 , … ∈ 𝐴, 𝑏1 , 𝑏2 , … ∈ 𝐵 とすると，マッチング 𝑀′ について
増大道は
𝑎1 → 𝑏1 → 𝑎2 → 𝑏2
と書ける．ここでマッチング 𝑀′は 𝑏1 , 𝑎2 であるが，
𝑀′は最大マッチングではない．
なぜなら，𝑀′′ = 𝑎1 , 𝑏1 , 𝑎2 , 𝑏2 ととったほうがマッチングの辺
の数が大きくなるからである．
27
事例１１
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
𝐴
𝐵
ではない
対偶を示す．対偶は，
マッチング𝑀に関する増大道が存在すれば，𝑀 は最大マッチング．
𝑎1 , 𝑎2 , … ∈ 𝐴, 𝑏1 , 𝑏2 , … ∈ 𝐵 とすると，マッチング 𝑀′ について関する
増大道は相異なる頂点およびを用いて
𝑎1 → 𝑏1 → 𝑎2 → 𝑏2
と書ける．ここでマッチング 𝑀′は 𝑏1 , 𝑎2 であるが，
𝑀′は最大マッチングではない．
なぜなら，𝑀′′ = 𝑎1 , 𝑏1 , 𝑎2 , 𝑏2 ととったほうがマッチングの辺
の数が大きくなるからである．
なぜ増大道の長さを３に限定したのか．また，マッチング 𝑀′ で
増大道に含まれない辺集合が考慮されていない．
28
模範解答
２部グラフの任意の最大マッチング 𝑀 に対し，
𝑀 に関する増大道が存在しないことを示せ．
𝐴
𝐵
背理法．最大マッチング 𝑀 に関する増大道
𝑃 = 𝑣0 , 𝑣1 , … , 𝑣𝑘 (𝑘 は奇数)が存在すると仮定する．
𝑋 = 𝑣𝑛 , 𝑣𝑛+1 𝑛 = 1,3, … , 𝑘 − 2 ,
𝑌 = 𝑣𝑛 , 𝑣𝑛+1 𝑛 = 0,2, … , 𝑘 − 1
とする．𝑀′ = 𝑀 ∖ 𝑋 ∪ 𝑌 とすれば，𝑀′ もマッチングである．
なぜならば，増大道の定義から，𝑣0 と 𝑣𝑘 は 𝑀 中に接続する
辺をもたず，辺集合 𝑌 中に互いに接続する2本の辺の組が
存在しないためである．
増大道の定義から，𝑋 ⊆ 𝑀, 𝑌 ∩ 𝑀 = ∅ であるから，
𝑀′ = 𝑀 − 𝑋 + 𝑌 ．
𝑋 < 𝑌 であるから， 𝑀′ > 𝑀 となり，M の最大性に矛盾．

Download Report