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

第９回
グラフ理論・組み合わせ論
情報学部門瀧本英二
http://www.i.kyushu-u.ac.jp/~eiji
平面的グラフ
クラトウスキー（Kuratowski）の定理の証明の続き
復習+𝛼
4
位相同型
定義 𝐺 が 𝐻 から辺の細分とその逆操作の繰り返し
で得られるとき，𝐺 と 𝐻 は位相同型であるという．
位相同型
5
クラトウスキー（Kuratowski）の定理
定理グラフ 𝐺 が非平面的グラフであるための必要
十分条件は 𝐺 が 𝐾5 または 𝐾3,3 と位相同型な部分
グラフを含むことである．
平面的グラフではない例
𝐾3,3 と位相同型な部分グラフ
6
𝑘連結（少し修正）
定義グラフ 𝐺 = (𝑉, 𝐸) が 𝑘連結
⇔ 𝑉 ≥ 𝑘 + 1，かつ
∀𝑆 ⊆ 𝑉: 𝑆 ≤ 𝑘 − 1,
𝐺 − 𝑆 ≡ 𝑉 − 𝑆, 𝑒 ∈ 𝐸 𝑒 ⊆ 𝑉 − 𝑆 が連結
（𝑘 − 1 個以下のどの頂点を削除しても連結）
このグラフは3連結
2連結でもある
（𝑘連結 ⇒ 𝑘 − 1連結）
最小次数が 3 なので，
4連結ではない
7
𝑘連結（別定義）
定義グラフ 𝐺 = (𝑉, 𝐸) が 𝑘連結
⇔ ∀𝑢, 𝑣 ∈ 𝑉 𝑢 ≠ 𝑣 ,
𝑢 と 𝑣 を結ぶ 𝑘 個の点素な
（𝑢 と 𝑣 以外同じ点を共有しない）道が存在．
𝑣
𝑢
𝑣
𝑢
8
辺縮約
定義：グラフ 𝐺 = (V, E) の辺 𝑒 = {𝑥, 𝑦} ∈ 𝐸 に対し，
辺 𝑒 を縮約したグラフ 𝐺/𝑒 とは，𝑥 と 𝑦 を新しい頂点
𝑣𝑒 におきかえ，𝑥 または 𝑦 に接続する辺 𝑒 ′ ∈ 𝐸 を
𝑣𝑒 に接続するように置き換えたグラフのことをいう．
𝐺
𝑥
𝑒
𝑦
𝐺/𝑒
𝑣𝑒
9
演習
グラフ 𝐺 = (𝑉, 𝐸) に対し，以下が成り立つことを示せ．
1. 𝐺 が連結 ⇔ ∀𝑒 ∈ 𝐸，𝐺/𝑒 が連結
2. ∀𝑒 ∈ 𝐸, ∀𝑆 ⊆ 𝑉 ∖ 𝑒, 𝐺 − 𝑆 𝑒 = 𝐺 𝑒 − 𝑆．
𝐺− 𝑧
𝑒
𝑒
𝑧
𝐺
𝐺/𝑒
𝑧
(𝐺 − 𝑧 ) 𝑒
=𝐺 𝑒− 𝑧
10
演習
3. ∀𝑒 = 𝑥, 𝑦 ∈ 𝐸, ∀𝑆 ⊆ 𝑉,
𝐺 − 𝑆 ∪ 𝑥, 𝑦 = 𝐺 𝑒 − 𝑆 ∪ 𝑣𝑒 ．
𝑥
𝑒
𝑦
𝑧
𝐺
𝑣𝑒
𝑧
𝐺/𝑒
𝐺 − 𝑥, 𝑦, 𝑧
= 𝐺 𝑒 − 𝑣𝑒 , 𝑧
11
証明の残り
補題１ ∀𝐺 = 𝑉, 𝐸 ，
𝐺 が3連結で 𝑉 ≥ 5 ⇒ ∃𝑒 ∈ 𝐸, 𝐺/𝑒 も3連結．
補題2 ∀𝐺 = 𝑉, 𝐸 ，
𝐺 が 𝐾5 または 𝐾3,3 と位相同型な部分グラフを持たない
⇒
∀𝑒 ∈ 𝐸, 𝐺/𝑒 も 𝐾5 または 𝐾3,3 と位相同型な部分グラフ
を持たない
補題の証明
13
補題１ ∀𝐺 = 𝑉, 𝐸 ，
𝐺 が3連結で 𝑉 ≥ 5 ⇒ ∃𝑒 ∈ 𝐸, 𝐺/𝑒 も3連結．
証明（背理法）
𝐺 は3連結， 𝑉 ≥ 5 だが，∀𝑒 ∈ 𝐸，𝐺/𝑒 は3連結ではないと仮定．
∀𝑒 ∈ 𝐸，𝐺/𝑒 からある2頂点を削除すると非連結．
【命題】その2頂点のうち1つは，縮約頂点 𝑣𝑒 である．
命題の証明（背理法）
• その2頂点からなる集合 𝑆 が 𝑣𝑒 を含まないと仮定．
• 𝐺 𝑒 − 𝑆 が非連結．よって演習の２より 𝐺 − 𝑆 𝑒 が非連結．
• よって演習の１より 𝐺 − 𝑆 が非連結．
• これは 𝐺 が３連結であることに矛盾．（命題の証明終）
14
補題１ ∀𝐺 = 𝑉, 𝐸 ，
𝐺 が3連結で 𝑉 ≥ 5 ⇒ ∃𝑒 ∈ 𝐸, 𝐺/𝑒 も3連結．
証明（背理法）
𝐺 は3連結， 𝑉 ≥ 5 だが，∀𝑒 ∈ 𝐸，𝐺/𝑒 は3連結ではないと仮定．
∀𝑒 ∈ 𝐸，𝐺/𝑒 からある2頂点を削除すると非連結．
【命題】その2頂点のうち1つは，縮約頂点 𝑣𝑒 である．
もう１つの頂点を辺 𝑒 の相棒と呼び，𝑧𝑒 と記す．
つまり， ∀𝑒 ∈ 𝐸，𝐺 𝑒 − 𝑣𝑒 , 𝑧𝑒 は非連結．
注：𝑒 の相棒 𝑧𝑒 は１つとは限らない．
演習の３より， 𝑒 = 𝑥, 𝑦 とすると，𝐺 − 𝑥, 𝑦, 𝑧𝑒 は非連結．
注：𝑒 の相棒が複数ある場合は，𝐺 − 𝑥, 𝑦, 𝑧𝑒 の最大の
連結成分が最大となるような 𝑧𝑒 を選ぶ．
このときの最大の連結成分の頂点数を 𝑛 𝑒 とおく．
15
補題１ ∀𝐺 = 𝑉, 𝐸 ，
𝐺 が3連結で 𝑉 ≥ 5 ⇒ ∃𝑒 ∈ 𝐸, 𝐺/𝑒 も3連結．
証明（つづき）
∀𝑒 = 𝑥, 𝑦 ∈ 𝐸, 𝐺 − 𝑥, 𝑦, 𝑧𝑒 は非連結．
𝐺 − 𝑥, 𝑦, 𝑧𝑒 の最大の連結成分の頂点数を 𝑛(𝑒) とおく．
以降では，𝑛(𝑒) が最大となる 𝑒 = 𝑥, 𝑦 とその相棒 𝑧𝑒 について
考える．𝐺 − 𝑥, 𝑦, 𝑧𝑒 の最大の連結成分を 𝐻 = 𝑉 ′ , 𝐸 ′ とおく．
つまり，𝑛 𝑒 = 𝑉 ′ ．
𝑉 ′′ = 𝑢 ∈ 𝑉 𝑧𝑒 , 𝑢 ∈ 𝐸, 𝑢 ∉ 𝑉 ′ , 𝑢 ∉ 𝑒 ≠ ∅ 【演習】
𝑢 ∈ 𝑉′′ を任意に選び，辺 𝑧𝑒 , 𝑢 の相棒を 𝑣 とおく．
𝑣 ∉ 𝑥, 𝑦 【演習】
𝑉 ′ ∪ 𝑥, 𝑦 ∖ 𝑣 は 𝐺 − 𝑧𝑒 , 𝑢, 𝑣 において連結している．【演習】
𝑉 ′ ∪ 𝑥, 𝑦 ∖ 𝑣 > 𝑛 𝑒 なので，𝑛(𝑒) の最大性に矛盾．
16
補題2 ∀𝐺 = 𝑉, 𝐸 ，
𝐺 が 𝐾5 または 𝐾3,3 と位相同型な部分グラフを持たない
⇒
∀𝑒 ∈ 𝐸, 𝐺/𝑒 も 𝐾5 または 𝐾3,3 と位相同型な部分グラフ
を持たない
証明（背理法）
∃𝑒 ∈ 𝐸, 𝐺/𝑒 が 𝐾5 または 𝐾3,3 と位相同型な部分グラフ 𝐻 を
含むと仮定．
𝑣𝑒 は 𝐻 において次数2ではない【演習】
以降では，𝐻 が 𝐾5 と位相同型な場合について証明する．
17
証明（つづき）
∃𝑒 = 𝑥, 𝑦 ∈ 𝐸, 𝐺/𝑒 が 𝐾5 と位相同型な部分グラフ 𝐻 を含む
と仮定
命題より，𝑣𝑒 の次数は４．
縮約前の部分グラフを 𝐻′ とする．
𝑣𝑒
𝑥
𝑒
𝑦
𝐻
縮約前の部分グラフ 𝐻′ の例
18
証明（つづき）
縮約前の部分グラフを 𝐻′ とする．
【場合１】 𝑥 （または 𝑦）の次数が 1 の場合．
𝐻′ − 𝑥 は 𝐾5 と位相同型．𝐻 ′ − 𝑥 は 𝐺 の部分グラフ
なので，仮定に反する．
【場合２】 𝑥 （または 𝑦）の次数が 2 の場合．
𝐻′ は 𝐾5 と位相同型なので，仮定に反する．
𝑥
𝐻′（場合１）
𝑥
𝑒
𝑒
𝑦
𝑦
𝐻′（場合２）
19
証明（つづき）
【場合３】 𝑥 および 𝑦 の次数が３以上の場合
（これ以降，次数２の頂点は無視し，６頂点のグラフと考える．）
𝑥 と 𝑦 の次数がちょうど３になるように適当に辺を削除
𝑥 を赤く塗って 𝑥 の隣接頂点を青く塗り，𝑦 の隣接頂点を赤く塗る．
両端点が同色の辺を削除すると，このグラフは 𝐾3,3 と位相同型．
これは 𝐺 の部分グラフなので，仮定に反する．
𝑥
𝐻′ （場合３）
𝑥
𝑥
𝑒
𝑒
𝑒
𝑦
𝑦
𝑦
20
補題2 ∀𝐺 = 𝑉, 𝐸 ，
𝐺 が 𝐾5 または 𝐾3,3 と位相同型な部分グラフを持たない
⇒
∀𝑒 ∈ 𝐸, 𝐺/𝑒 も 𝐾5 または 𝐾3,3 と位相同型な部分グラフ
を持たない
証明（背理法）
∃𝑒 ∈ 𝐸, 𝐺/𝑒 が 𝐾5 または 𝐾3,3 と位相同型な部分グラフ 𝐻 を
含むと仮定．
𝐻 が 𝐾5 と位相同型な場合について，矛盾を導いた．
𝐻 が 𝐾3,3 と位相同型な場合についても，同様に矛盾を導け．
【演習】
21
外平面的グラフ
定義グラフ 𝐺 が外平面的であるとは，𝐺 のすべての
頂点が外面に接するように平面描画できるときをいう．
外平面的グラフの例
左のグラフの外平面描画
22
外平面的グラフの特徴づけ１
定義グラフ 𝐺 = 𝑉, 𝐸 に対し，
𝐺 + 𝐾1 = 𝑉 ∪ 𝑣0 , 𝐸 ∪
ただし，𝑣0 ∉ 𝑉．
𝑣, 𝑣0
𝑣∈𝑉
，
𝑣0
𝐺
𝐺 + 𝐾1
23
外平面的グラフの特徴づけ１
定理
グラフ 𝐺 = 𝑉, 𝐸 が外平面的 ⇔ 𝐺 + 𝐾1 が平面的
𝑣0
𝐺
𝐺 + 𝐾1
24
外平面的グラフの特徴づけ２
定理
グラフ 𝐺 = 𝑉, 𝐸 が外平面的でない ⇔
𝐺 が 𝐾4 または 𝐾2,3 と位相同型な部分グラフを持つ
𝐾4
𝐾2,3

Download Report