2015年度 有限幾何学 中間試験
問1 次の用語の定義を書け．
(1) オイラー回路 (2) ハミルトン閉路
問2 次の問に答えよ． （ただし，握手補題，オイラーの定理，Oreの定理 は授業で紹介したものとする）
(1) 握手補題を書け．
(2) オイラーの定理を書け．
(3) Oreの定理を書け．
(4) 下図のような正方形のタイルがいくつか敷き詰められている状況で，
これらのタイルを赤と黒に塗り分けることを考える．
全ての赤に塗られたタイルに対して，隣接する赤に塗られたタイルの個数が奇数であるとき，
赤に塗られたタイルの総数は偶数であることを示せ．
（握手補題を用いてもよい）
(5) 奇点の個数が2であることがオイラー小道を持つための必要十分条件であることを証明せよ．
（ オイラーの定理を用いてもよい）
(6) 位数nのグラフGの任意の非隣接な2頂点uとvに対して，dG(u)+dG(v)≧n-1ならばGはハミルトン道を持つことを証明せよ．
（Oreの定理を用いてもよい）
(7) 位数nのグラフGで，任意の非隣接な2頂点uとvに対してdG(u)+dG(v)≧n-1であるがハミルトングラフではない例を書け．
また，書いたグラフがなぜハミルトングラフではないのかを説明せよ．
問3 下図の重み付きグラフの全ての辺を通る重み最小の閉歩道の重みを求めよ．
3
2
1
3
1
4
1
2
3
3
2
3
2
1
2
2
4

スライド 1

スライド 1

情報とコンピュータ

生体システム概論

現代文 B

自分の価値観で人を責めない 一つの失敗で全て否定しない 長所を見て

刑事政策演習

未就園児 傷害保険加入のお願い

中間試験の問題と略解

詳細はこちら - 東京電業協会

第 69 回入学式 近賀ゆかり選手来校 4/7（火）

チーム・選手登録の流れ (PDF 456KB)

この演習に関する概説

単位認定方法・評価 （単位について） ①単位の構成 授業科目は、授業の

日本史

ニセコ東急ゴルフコース 2015年度『HANAZONO友の会』入会申込書

2015年度 国の学童保育予算(案)の単価 修正版

情報科学序論

コンクリート構造学I ガイダンス

有機化学 II （後期）中間試験（武田）11/27/14（その1） 番号 氏名 (1) (2

JMA大学SDフォーラム - 社団法人・日本能率協会（JMA）

アクティブシニア 合同就職面接会の開催について