第2回レポート問題解答 - lab.twcu.ac.jp

第 2 回レポート問題解答
幾何学とグラフ (担当: 新國)
2015 年 7 月 3 日 (金) 配付
問題.
以下の大問 1 , 2 , 3 の全てに解答せよ.
1 図 1 のグラフ G1 が平面的であるかどうか判定せよ.
1
5
9
7 8
6
4
2
3
図 1: グラフ G1
2 図 2 の完全グラフ K8 のジェネリックなはめ込み f : K8 → R2 で, cr(f ) = 18
となるものの絵を描け.
1
8
2
7
3
6
4
5
図 2: K8
1
3 図 3 のグラフ G2 の最小交差数を求めよ.
1
4
6
5
2
7
3
8
図 3: グラフ G2
以上
解答.
1 例えば図 4 に示したように, G1 は R2 上に辺の交差なく描けるので, G1 の R2 へ
の埋め込みが存在する. 従って G1 は平面的である.
1
1
5
9
7 8
6
2
9
4
f
6
8
7
4
2
3
5
3
図 4: 埋め込み f : G1 → R2
2 例えば, 図 5 に示したジェネリックなはめ込み f : K8 → R2 において, cr(f ) = 18
である1 .
1 定理 2.5.10 で述べた通り, K の最小交差数は 18 であることが既に知られているのであった. つまり, 例えば図 5 の
8
f は, K8 の最小交差数を実現するはめ込みである.
2
4
1
f
K8
5
8
6
7
2
3
図 5: cr(f ) = 18 なるジェネリックなはめ込み f : K8 → R2
3 以下, グラフ G の最小交差数を cr(G) と表す. まず, G2 から辺 1 5 を取り除い
て得られる部分グラフは, K3,3 の細分である (図 6 を参照). 従って G2 は平面的で
ないので,
cr(G2 ) ≥ 1
(i)
である.
1
1
7
8
6
4
4
6
2
3
6
1
5
5
5
7
8
2
7
3
8
2
4
3
図 6: G2 は K3,3 の細分を部分グラフとして含む
一方, 例えば図 7 に示したように, G2 の R2 への cr(f ) = 1 なるジェネリックなは
め込み f : G2 → R2 が存在する. 即ち
cr(G2 ) ≤ 1
3
(ii)
である.
8
1
4
7
f
4
6
1
5
5
2
3
7
3
8
6
2
図 7: cr(f ) = 1 なるジェネリックなはめ込み f : G2 → R2
故に (i), (ii) から, cr(G2 ) = 1 である.
4

Download Report