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