グラフ理論・組み合わせ論

第１０回
グラフ理論・組み合わせ論
情報学部門瀧本英二
http://www.i.kyushu-u.ac.jp/~eiji
存在性証明
鳩ノ巣原理（Pigeonhole Principle）
確率的論法（Probabilistic Argument）
3
存在定理と非構成的証明
𝐷：集合
𝐴：𝐷 → {𝑇𝑟𝑢𝑒, 𝐹𝑎𝑙𝑠𝑒} （𝐷上の述語）
に対し，
“∃𝑑 ∈ 𝐷, 𝐴 𝑑 = 𝑇𝑟𝑢𝑒”
という形の命題を，一般に存在定理という．
構成的証明： 𝐴 𝑑 = 𝑇𝑟𝑢𝑒 を満たす要素 𝑑 ∈ 𝐷 を
具体的に示すことによる証明．
非構成的証明：そのような要素を陽に示さない証明．
主な証明法として，鳩ノ巣原理や確率的論法がある．
4
構成的証明の例
定理： ∀𝑥 ∈ ℕ, ∃𝑦 ∈ ℕ, 𝑦 > 𝑥 ∧ 𝑝𝑟𝑖𝑚𝑒 𝑦
（素数は無数に存在する）
証明
𝑥 ∈ ℕ を任意に固定．
𝑦 を 𝑥! + 1 の最小の素因数とする． ← 構成的
𝑝𝑟𝑖𝑚𝑒(𝑦) は明らか
2 ≤ ∀𝑧 ≤ 𝑥, 𝑥! + 1 mod 𝑧 = 1
すなわち 𝑧 は 𝑥! + 1 の約数（素因数）ではない
よって，𝑦 > 𝑥
5
鳩ノ巣原理
𝐷, 𝑌：集合（𝑛 = 𝐷 , 𝑘 = |𝑌|）
∀𝑓: 𝐷 → 𝑌, ∃𝑦 ∈ 𝑌, 𝑓 −1 𝑦
≥ 𝑛/𝑘
どれかの巣に
5/2 = 3羽
以上の鳩が入る
6
Erdős の天才を見分ける法
200以下の自然数が101個あるとする．以下の２つの
命題は正しいか？
【命題１】互いに素（最大公約数が１）な2つの数が
必ずある．
【命題２】 𝑎 が 𝑏 で割り切れるような2つの数 𝑎, 𝑏 が
必ずある．
7
命題１の証明
𝐷 ⊆ 𝑥 ∈ ℕ 𝑥 ≤ 200 , D = 101
𝑌 = 1,2, … , 100
𝑓 𝑥 = 𝑥/2
：𝐷の
要素
1
2
3
4
5
6
7
8
9
10
1
2
3 𝑌
どれかの 𝑦 ∈ 𝑌 に
２つの 𝐷 の要素が対応
その要素とは，2𝑦 − 1 と 2𝑦
これらは互いに素
4
5
【演習】
命題２の真偽を判定せよ
8
講義資料１の演習２
定理
𝑉 ≥ 2 を満たす任意の無向グラフ 𝐺 = 𝑉, 𝐸
に対し，ある 2頂点 𝑢, 𝑣 ∈ 𝑉(𝑢 ≠ 𝑣) が存在して，
𝑑𝐺 𝑢 = 𝑑𝐺 (𝑣)
が成り立つ
証明 𝑛 = 𝑉 とおく．
𝑑𝐺 : 𝑉 → 0,1, … , 𝑛 − 1 に注意．
𝑑𝐺 𝑢 = 0 かつ 𝑑𝐺 𝑣 = 𝑛 − 1 を満たす 𝑢, 𝑣 ∈ 𝑉
は存在しない．
よって，∃𝑌 ⊆ 0,1, … , 𝑛 − 1 , 𝑌 = 𝑛 − 1,
𝑑𝐺 : 𝑉 → 𝑌 とみなせる．
9
[Erdős, Szekeres ’35]
定理相異なる 𝑛 = 𝑘 2 + 1 個の実数からなる数列
𝑎1 , 𝑎2 , … , 𝑎𝑛
は，長さ 𝑘 + 1 の増加部分列
𝑎𝑖1 < 𝑎𝑖2 < ⋯ < 𝑎𝑖𝑘+1 (𝑖1 < 𝑖2 < ⋯ < 𝑖𝑘+1 )
か長さ 𝑘 + 1 の減少部分列
𝑎𝑖1 > 𝑎𝑖2 > ⋯ > 𝑎𝑖𝑘+1 (𝑖1 < 𝑖2 < ⋯ < 𝑖𝑘+1 )
例（𝑘 = 3, 𝑛 = 10）
6, 9, 4, 8, 1, 12, 5, 10, 3, 7
10
証明
𝑓 𝑖 = 𝑢𝑖 , 𝑣𝑖 , ただし
𝑢𝑖 = 𝑎𝑖 から始まる最長増加部分列長
𝑣𝑖 = 𝑎𝑖 から始まる最長減少部分列長
𝑖
𝑎𝑖
1
2
3
4
5
6
7
8
9
10
6
9
4
8
1
12
5
10
3
7
𝑢𝑖
𝑣𝑖
3
3
2
4
3
2
2
3
3
1
1
3
2
2
1
2
2
1
1
1
∃𝑖, 𝑢𝑖 ≥ 𝑘 + 1 または 𝑣𝑖 ≥ 𝑘 + 1
を示せばよい．
【背理法】 ∀𝑖, 1 ≤ 𝑢𝑖 , 𝑣𝑖 ≤ 𝑘 と仮定
11
証明
すると，𝑓: 1, … , 𝑘 2 + 1 → 1, … , 𝑘 × 1, … , 𝑘 ．
鳩ノ巣原理より，
∃𝑖, 𝑗 𝑖 < 𝑗 , 𝑢𝑖 , 𝑣𝑖 = 𝑢𝑗 , 𝑣𝑗
しかし，それはありえない．（【演習】）
1
2
𝑖
𝑗
𝑘2 + 1
𝑎1
𝑎2
𝑎𝑖
𝑎𝑗
𝑎𝑘 2 +1
𝑢𝑖
3
3
𝑣𝑖
2
2
12
鳩ノ巣原理の確率的解釈
１つの巣に入る鳩の数の平均は 𝑛/𝑘
すなわち，確率変数 𝑋 を，
一様ランダムに選んだ巣 𝑖 に
いる鳩の数 𝑓 −1 𝑖 とすると，
𝐸 𝑋 = 𝑛/𝑘．
一般に，任意の確率変数 𝑍 に
対し，𝑃 𝑍 ≥ 𝐸 𝑍 > 0．すなわち
𝑛
Z ≥ 𝐸 𝑍 を満たす事象が存在する
よって，𝑛/𝑘 以上の鳩がいる巣 𝑖 が存在する
𝑘
→ これを一般化したのが確率的論法
確率的論法
存在定理
“∃𝑑 ∈ 𝐷, 𝐴 𝑑 = 𝑇𝑟𝑢𝑒”
を示す方法の枠組み
1.
2.
𝐷 上に適当な確率分布 𝑝 を定義
𝑃𝑥∼𝑝 𝐴 𝑥 = 𝑇𝑟𝑢𝑒 > 0 を示す．
確率的論法の適用例
定理：任意の無向グラフ 𝐺 に対し，高々半数の辺を
削除することにより，二部グラフが得られる．
命題： 𝐺 が二部グラフ ⇔ 𝐺 が２彩色可能
隣接頂点が異なる色に
なるように，すべての頂点を
２色で塗り分けること
確率的論法の適用例
証明 𝐺 = 𝑉, 𝐸 の辺の数を 𝑚 とする．
各頂点を一様ランダムに赤か青で塗る．
すなわち，𝐷 = 𝑐: 𝑉 → 𝑟𝑒𝑑, 𝑏𝑙𝑢𝑒 上の一様分布
に従って，彩色 𝑐: 𝑉 → 𝑟𝑒𝑑, 𝑏𝑙𝑢𝑒 を選ぶ．
このとき，両端点が同色の辺の集合を 𝑀 𝑐 とおく．
すなわち，𝑀 𝑐 = 𝑢, 𝑣 ∈ 𝐸 𝑐 𝑢 = 𝑐 𝑣 ．
𝐸 𝑀 𝑐 = 𝑚/2．
よって，∃𝑐 ∈ 𝐷, 𝑀 𝑐 ≤ 𝑚/2．
𝑀 𝑐 の辺を全部削除することにより，𝑐 は残った
グラフの２彩色になっている．
よって，残ったグラフは二部グラフ．
例２：独立集合のサイズ
定理：任意の無向グラフ 𝐺 = 𝑉, 𝐸 , 𝑛 = 𝑉 に対し，
𝐸 ≤ 𝑛𝑘/2 ならば，∃𝑉 ′ ⊆ 𝑉, 𝑉 ′ ≥ 𝑛/(2𝑘),
∀𝑢, 𝑣 ∈ 𝑉 ′ , 𝑢, 𝑣 ∉ 𝐸 （𝑉′ は独立集合）
𝑉′ =
は独立集合
証明
𝑉 ′ ⊆ 𝑉 に対し，𝐸𝑉 ′ = 𝑢, 𝑣 ∈ 𝐸 𝑢, 𝑣 ∈ 𝑉 ′ と定義．
各頂点 𝑢 ∈ 𝑉 に対し，独立に
𝑃 𝑢 ∈ 𝑉 ′ = 1/𝑘
となるように，ランダムに頂点部分集合 𝑉′ を選ぶ．
明らかに，𝐸 𝑉 ′ = 𝑛/𝑘．
また，任意の 𝑢, 𝑣 ∈ 𝐸 に対し，
𝑃 𝑢, 𝑣 ∈ 𝐸𝑉 ′ = 𝑃 𝑢 ∈ 𝑉 ′ , 𝑣 ∈ 𝑉 ′ = 1/𝑘 2
より，𝐸 𝐸𝑉 ′
よって，𝐸
𝑉′
=
𝐸
𝑘2
≤
− 𝐸𝑉 ′
𝑛
．
2𝑘
=𝐸
𝑉′
− 𝐸 𝐸𝑉 ′
𝑛
≥
𝑛
．
2𝑘
すなわち，∃𝑉 ′ ⊆ 𝑉, 𝑉 ′ − 𝐸𝑉 ′ ≥ ．
2𝑘
各辺 𝑢, 𝑣 ∈ 𝐸𝑉 ′ に対し，𝑢 か 𝑣 を削除して得られる
頂点集合を 𝑉′′ とすると，𝐸𝑉 ′′ = ∅ （𝑉′′ は独立集合），かつ
𝑛
′′
′
𝑉 ≥ 𝑉 − 𝐸𝑉 ′ ≥
．
2𝑘

Download Report