中間試験の問題と略解

2016年度有限幾何学中間試験
問1 次のグラフを描け．（描けない場合は理由を述べよ）各20点
(1) 次数として，1,1,2,2,3 の数をもつグラフ
(2) K1,3を誘導部分グラフとして含む正則グラフ
問2 次の問に答えよ．（ただし，オイラーの定理は授業で紹介したものとする）各20点
(1) 奇点の個数が2であることがオイラー小道を持つための必要十分条件であることを証明せよ．
（オイラーの定理を用いてもよい）
(2) Gを位数nのハミルトングラフとし，ある2頂点u,v∊V(G)に対し，uv∊E(G)かつdG(u)+dG(v)≧n+2であるとする．
このとき，G-uvもハミルトングラフであることを証明せよ．
問3 下図の重み付きグラフについて，次の各問に答えよ．（答えのみでよい）各10点
(1) 重み最小のA-B 道とその重さを求めよ．
(2) 全ての辺を通る重み最小の閉歩道の重さを求めよ．
E
2
5
2
1
A
2
4
3
C
D
2
3
1
6
F
B
2016年度有限幾何学中間試験略解
問2(2)以外は簡単なので省略
問2
(2) Gを位数nのハミルトングラフとし，ある2頂点u,v∊V(G)に対し，uv∊E(G)かつdG(u)+dG(v)≧n+2であるとする．
このとき，G-uvもハミルトングラフであることを証明せよ．
（ヒント：Oreの定理の証明）
略証：
Gを位数nのハミルトングラフとし，
ある2頂点u,v∊V(G)に対し，uv∊E(G)かつdG(u)+dG(v)≧n+2であるとする．
G-uvがハミルトングラフではないと仮定する．
CをGのハミルトンサイクルとする．
Cがuvを通らないならば，CがG-uvのハミルトンサイクルとなり矛盾．
よって，Cはuvを通る．
よって，G-uvは全ての頂点を通り，uとvを端点とする道P（=C-uv）を持つ．
また，
dG-uv(u)+dG-uv(v)≧(n+2)-2=n・・・(1)
が成立．
以下Oreの定理の証明と同じ

Download Report