スライド 1

2012年度有限幾何学期末試験
次の各問に答えよ．
(1) 頂点数と辺の数が等しい連結グラフが丁度一つの閉路を持つことを示せ．
(2) 次数がkの頂点をl個持つ木は次数1の頂点を少なくとも(k-2)l+2個持つことを示せ．
(3) 強連結なトーナメントが長さ3の有向閉路を持つことを示せ．
(4) 位数3以上の連結単純平面グラフGに対し，Gが長さ3の閉路を持たないならば|E(G)|≦2|V(G)|-4であることを示せ．
(5) 長さ3の閉路を持たない単純平面グラフが次数3以下の頂点を持つことを示せ．
(6) 長さ3の閉路を持たない単純平面グラフが4-彩色可能であることを示せ．
(7) 図1のグラフの最小全域木を描き，その重さも答えよ．
(8) 重み 1，3，5，7，8 に対する総コード長が最小の2分木を描き，その総コード長も答えよ．
(9) 図2のグラフはK3,3の細分を部分グラフとして含む．このグラフを図示せよ．
(10) 図2のグラフの交差数を求めよ．（理由も書くこと）
b
7
9
a
5
7
f
9
g
8 14
3
d
図1
b
c
6
12
16
c
a
21
h
7
9
2
e
d
e
g
f
図2

Download Report