スライド 1

2012年度有限幾何学中間試験
問1 次の用語の定義をそれぞれ述べよ．
(1) オイラー回路
(2) ハミルトン閉路
(3) オイラー小道
(4) ハミルトン道
問2 授業で紹介した次の定理を書け．
(1) 握手補題
(2) オイラーの定理
(3) Oreの定理
(4) Diracの定理
(5) BondyとChvatalによる閉包に関する定理
問3 次の問に答えよ．（ただし，オイラーの定理，Oreの定理，Diracの定理は授業で紹介したものとする）
奇点の数が2であることがオイラー小道を持つための必要十分条件であることを，オイラーの定理を用いて証明せよ．
Oreの定理を用いてDiracの定理を証明せよ．
Kl.mのBondy-Chvatal閉包C(Kl,m)を描け．
グラフGに対し，任意の空ではない S⊆V(G) に対し，k(G-S)≦|S|+1であることが
Gがハミルトン道を持つための必要条件であることを証明せよ．（k(G-S)はG-Sの連結成分の数を表す）
(5) Kl,m がハミルトン道を持つための必要十分条件を求めよ．（証明も書け）
(1)
(2)
(3)
(4)
問4 次のグラフをそれぞれ一つずつ描け．また，描けない場合はその理由を述べよ．
(1)
(2)
(3)
(4)
(5)
オイラー小道とオイラー回路を共に持つ位数8のグラフG1
Oreの定理の仮定を満たすがDiracの定理の仮定を満たさない位数6の単純グラフG2
位数7の3-正則グラフG3
ある空ではない S⊆V(G4) に対し，k(G4-S)=|S|+1であるハミルトングラフではない位数5の単純グラフG4
K1,3を誘導部分グラフとして持たない連結グラフでハミルトングラフではない位数5の単純グラフG5
問5 次の重み付きグラフにおける全ての辺を通る重み最小の閉歩道とその重みを書け．
a
5
f
4
b
1
1
2
2
2
3
d
2
3
c
6
e

Download Report