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 1 3 6 5 4 B A C D F
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の定理の証明と同じ