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

第８回
グラフ理論・組み合わせ論
情報学部門瀧本英二
http://www.i.kyushu-u.ac.jp/~eiji
平面的グラフ
クラトウスキー（Kuratowski）の定理の証明
復習
4
平面図の性質２
定理平面グラフ 𝐺 の外面でない任意の面 𝑓 に
対し，𝑓 が外面になるような 𝐺 の平面図が存在．
3
1
3
𝑓1
4
2
6
𝑓3
𝑓4
𝑓2
𝑓5
𝑓3
𝑓6
5
7
4
1
𝑓1
𝑓6
6
𝑓5
2
𝑓2
7
𝑓4
5
5
オイラーの公式
定理：連結である平面グラフ 𝐺 に対して，次の等式
が成り立つ．ここで，𝑝, 𝑞, 𝑟 は，それぞれ 𝐺 の頂点数，
辺数，面数を表す．
𝑝−𝑞+𝑟 =2
𝑝 = 7, 𝑞 = 11, 𝑟 = 6
6
平面グラフの疎性
定理任意の平面グラフ 𝐺 に対し，𝑝 ≥ 3 ならば
𝑞 ≤ 3𝑝 − 6．
系完全グラフ 𝐾5 は平面的ではない．
𝐾5
7
平面的2部グラフの疎性
定理任意の平面的２部グラフ 𝐺 に対し，𝑝 ≥ 3 ならば
𝑞 ≤ 2𝑝 − 4．
系完全2部グラフ 𝐾3,3 は平面的ではない．
𝐾3,3
9
細分
定義グラフ 𝐻 の辺 {𝑦, 𝑧} に対して，辺 {𝑦, 𝑧} を削除し，
新しい頂点 𝑥 と新しい2つの辺 {𝑦, 𝑥} と {𝑥, 𝑧} を加えて
得られるグラフ 𝐺 を 𝐻 の辺 {𝑦, 𝑧} を細分してできる
グラフという．
𝑦
𝑦
𝑥
細分
𝑧
𝐻
𝑧
𝐺
10
位相同型
定義 𝐺 が 𝐻 から辺の細分とその逆操作の繰り返し
で得られるとき，𝐺 と 𝐻 は位相同型であるという．
位相同型
11
クラトウスキー（Kuratowski）の定理
定理グラフ 𝐺 が非平面的グラフであるための必要
十分条件は 𝐺 が 𝐾5 または 𝐾3,3 と位相同型な部分
グラフを含むことである．
平面的グラフではない例
𝐾3,3 と位相同型な部分グラフ
12
証明の流れ
十分性
𝐾5 または 𝐾3,3 と位相同型な部分グラフを含む
⇒ 平面的グラフではない
は明らか．
必要性（の対偶）
𝐾5 または 𝐾3,3 と位相同型な部分グラフを含まない
⇒ 平面的グラフ
を，頂点数 𝑝 に関する帰納法で示す．
𝑝 ≤ 4 のときは自明．
𝐺 = (𝑉, 𝐸) を頂点数 𝑝 ≥ 5 で 𝐾5 または 𝐾3,3 と位相
同型な部分グラフを含まない連結グラフと仮定し，
𝐺 が平面的であることを示す．
13
場合分け
次の３つの場合について，それぞれ証明する．
1. 𝐺 が２連結でない
2. 𝐺 が２連結だが３連結でない
3. 𝐺 が３連結
定義グラフ 𝐺 = (𝑉, 𝐸) が 𝑘連結
⇔ ∀𝑆 ⊆ 𝑉: 𝑆 = 𝑘 − 1,
𝐺 ′ = 𝑉 − 𝑆, 𝑒 ∈ 𝐸 𝑒 ⊆ 𝑉 − 𝑆
（どの 𝑘 − 1 頂点を削除しても連結）
が連結
14
1. 𝐺 が2連結でない場合
ある頂点 𝑥 を削除すると非連結．
すなわち，頂点集合の分割 𝑉 = 𝑉1 ∪ 𝑥 ∪ 𝑉2 が存在し，
𝐸1 = 𝑒 ∈ 𝐸 𝑒 ⊆ 𝑉1 ∪ 𝑥
𝐸2 = 𝑒 ∈ 𝐸 𝑒 ⊆ 𝑉2 ∪ 𝑥
とすると，𝐸 = 𝐸1 ∪ 𝐸2 , 𝐸1 ∩ 𝐸2 = ∅．
𝐺1 = 𝑉1 ∪ 𝑥 , 𝐸1 , 𝐺2 = 𝑉2 ∪ 𝑥 , 𝐸2 は 𝐺 の部分
グラフなので，𝐾5 または 𝐾3,3 と位相同型な部分グラフ
を含まず，それぞれの頂点数は 𝑝 − 1 以下．
よって，帰納法の仮定より 𝐺1 , 𝐺2 は平面的．
特に，平面図の性質２より，それぞれ 𝑥 が外平面に接する
ような平面図が描ける．
各平面図の 𝑥 を同一頂点にマージすることにより，𝐺 の
平面図を得る．
15
2. 𝐺 が2連結だが3連結でない場合（1/2）
ある2頂点 𝑥, 𝑦 を削除すると非連結．
すなわち，頂点集合の分割 𝑉 = 𝑉1 ∪ 𝑥, 𝑦 ∪ 𝑉2 が存在し，
𝐸1 = 𝑒 ∈ 𝐸 𝑒 ⊆ 𝑉1 ∪ 𝑥, 𝑦 ∪ 𝑥, 𝑦
𝐸2 = 𝑒 ∈ 𝐸 𝑒 ⊆ 𝑉2 ∪ 𝑥, 𝑦 ∪ 𝑥, 𝑦
とすると，𝐸 ∪ 𝑥, 𝑦 = 𝐸1 ∪ 𝐸2 , 𝐸1 ∩ 𝐸2 = 𝑥, 𝑦 ．
𝐺1 = 𝑉1 ∪ 𝑥, 𝑦 , 𝐸1 , 𝐺2 = 𝑉2 ∪ 𝑥, 𝑦 , 𝐸2 とする．
補題 𝐺1 , 𝐺2 は 𝐾5 または 𝐾3,3 と位相同型な部分
グラフを含まない．
よって，帰納法の仮定より，𝐺1 , 𝐺2 は平面的．特に，辺 𝑥, 𝑦 が
外平面に接するような平面図が描ける．
各平面図の辺 𝑥, 𝑦 をマージすることにより 𝐺 ∪ 𝑥, 𝑦 の
平面図，すなわち 𝐺 の平面図を得る．
16
2. 𝐺 が2連結だが3連結でない場合（2/2）
補題 𝐺1 , 𝐺2 は 𝐾5 または 𝐾3,3 と位相同型な部分
グラフを含まない．
証明
𝑥, 𝑦 ∈ 𝐸 のときは，𝐺1 , 𝐺2 が 𝐺 の部分グラフなので自明．
𝑥, 𝑦 ∉ 𝐸 のとき，𝐺1 が 𝐾5 または 𝐾3,3 と位相同型な部分
グラフ 𝐻 を含むと仮定（背理法）．
𝐻 は 𝑥, 𝑦 を辺として含むはず．
𝐺 は2連結なので，𝐺2 に 𝑥 と 𝑦 を結ぶ道が存在する．【演習】
辺 𝑥, 𝑦 をこの道で置き換えたグラフ 𝐻′ も 𝐾5 または 𝐾3,3 と
位相同型
𝐻′ は 𝐺 の部分グラフなので，仮定に反する．
17
3. 𝐺 が3連結の場合
Tutte の定理 𝐺 が3連結で，𝐾5 または 𝐾3,3 と位相
同型な部分グラフを含まないならば，𝐺 は平面的．
注：各面が凸多角形であり，どの3点も直線上にない
ように描画できることを示している．
まとめ
いずれの場合も 𝐺 が平面的であることが示せたので，
Kuratowski の定理が証明できた．
18
Tutte の定理の証明の準備：辺縮約
定義：グラフ 𝐺 = (V, E) の辺 𝑒 = {𝑥, 𝑦} ∈ 𝐸 に対し，
辺 𝑒 を縮約したグラフ 𝐺/𝑒 とは，𝑥 と 𝑦 を新しい頂点
𝑣𝑒 におきかえ，𝑥 または 𝑦 に接続する辺 𝑒 ′ ∈ 𝐸 を
𝑣𝑒 に接続するように置き換えたグラフのことをいう．
𝐺
𝑥
𝑒
𝑦
𝐺/𝑒
𝑣𝑒
19
Tutte の定理の証明
以下の２つの補題を用いる．
補題１ ∀𝐺 = 𝑉, 𝐸 ，
𝐺 が3連結で 𝑉 ≥ 5 ⇒ ∃𝑒 ∈ 𝐸, 𝐺/𝑒 も3連結．
補題2 ∀𝐺 = 𝑉, 𝐸 ，
𝐺 が 𝐾5 または 𝐾3,3 と位相同型な部分グラフを持たない
⇒
∀𝑒 ∈ 𝐸, 𝐺/𝑒 も 𝐾5 または 𝐾3,3 と位相同型な部分グラフ
を持たない
補題の証明は後回し
20
Tutte の定理の証明
頂点数に関する帰納法を用いる．
頂点数 𝑉 ≤ 4 のときは自明なので， 𝑉 ≥ 5 と仮定．
補題１，２より， ∃𝑒 ∈ 𝐸, 𝐺/𝑒 は3連結であり，
𝐾5 または 𝐾3,3 と位相同型な部分グラフを持たない
帰納法の仮定より，𝐺/𝑒 は平面的．
𝑒 を縮約した点 𝑣𝑒 が 𝐺/𝑒 の内部の面に接するように
描画する．
この描画から，𝐺 の平面図を構成する．
21
Tutte の定理の証明
頂点 𝑣𝑒 が，頂点 𝑧0 , 𝑧1 , … , 𝑧𝑚−1 と，時計まわりにこの順で
隣接しているとする．
𝑧𝑖 と 𝑧𝑖+1 を結ぶ境界と
𝑧0
𝑧𝑗 と 𝑧𝑗+1 を結ぶ境界は
共通の頂点を持たない．
𝑧
𝑧
1
𝑚−1
𝑣𝑒
𝑧2
𝑧3
もし，そのよう
この面には
な頂点があれ 𝑧𝑖 頂点がない
zi+1
ば，𝑧𝑖 に最も近い
そのような頂点と
𝑣𝑒 の2頂点を
zj
𝑣𝑒
削除すると，ziと
この面には
zi+1 が連結でなくなる．頂点がない
zj+1
これは 𝐺/𝑒 が
3連結であることに反す．
22
Tutte の定理の証明
頂点 𝑣𝑒 の隣接頂点がちょうど3個のとき，𝑣𝑒 をもとの辺 𝑥, 𝑦 に
戻したとき，次の図のようになれば，𝐺 は 𝐾5 と位相同型な部分
グラフを含むことになり，仮定に反する．これ以外の場合は平面
に描くことができる．
𝑣𝑒
x
y
23
Tutte の定理の証明
頂点 𝑣𝑒 の隣接頂点が4個以上のとき，𝑣𝑒 をもとの辺 𝑥, 𝑦 に
戻したとき，𝑥 の隣接頂点と 𝑦 の隣接頂点が交互にならぶような
4点があれば，𝐺 は 𝐾3,3 と位相同型な部分グラフを含むことになり，
仮定に反する．
𝑧0
zp
zs
𝑧1
𝑧
𝑚−1
𝑣𝑒
x
𝑧2
𝑧3
zr
y
zq
24
Tutte の定理の証明
よって，前スライドのような４頂点は存在しない．
この場合，下図のように平面描画可能．
x
y

Download Report