2017年度 有限幾何学 期末試験 注意：ループと多重辺がないグラフのみを扱う． 問1 次の定理と，その証明の概略を読み，各問に答えよ．

Presentation on theme: "2017年度 有限幾何学 期末試験 注意：ループと多重辺がないグラフのみを扱う． 問1 次の定理と，その証明の概略を読み，各問に答えよ．"— Presentation transcript:

1 2017年度 有限幾何学 期末試験 注意：ループと多重辺がないグラフのみを扱う． 問1 次の定理と，その証明の概略を読み，各問に答えよ． 定理：Gを3角形がない平面的グラフとする．このとき，Gが4-彩色可能である． 証明の概略： Gを3角形がない平面的グラフとする． |V(G)|に関する帰納法で証明する． |V(G)|=1の場合は明らか． 以下|V(G)|≧2とし，位数が|V(G)|未満のグラフに対して定理が成立すると仮定する． Gは3角形がない平面的グラフなので，|E(G)|<2|V(G)|．① よって，Gに次数が3以下の頂点vが存在する．② 　　　　　　　　③　　　　　　　なのでG-vに帰納法の仮定を適用することができ， G-vが　　　　　　　　④　　　　　　　であることが分かる． vの次数が3以下なので，　　　　　　　　　　　　⑤　　　　　　　　　　　ができるので，Gが4-彩色可能であることが分かる． 下線部①は自明ではない．以下の文章は正しい理由を説明したものである． この文章を読み，⑥，⑦，⑧に当てはまる文章か数字か式をそれぞれ書け． Gを3角形がない平面グラフとし，fi（1≦i≦r）をGの各領域の境界上の辺の本数とする． 　　　　　　 　⑥　　　　　　　 なので，Σ1≦i≦rfi ≧ ⑦ r． よって， 2|E(G)|=Σ1≦i≦rfi ≧ ⑦ r となるので，オイラーの公式より， 4|V(G)|= 　　　　⑧　　　　>2|E(G)|， ∴　|E(G)|<2|V(G)|であることが分かる． 下線部②は自明ではない．正しい理由を書け． (3)　③，④，⑤に当てはまる文章をそれぞれ書け． 問2 次の問題を読み，解答の空欄を埋めよ．（⑥は途中計算も書くこと） 問題： 2n個のチームが 2n-1 日間にわたり，次のように総当たりトーナメント形式の試合を行う． 各チームは他のいずれかのチームと1日1回試合を行う． 試合には引き分けがない． このとき，2n-1日間のそれぞれの日から勝ったチームを重なりがないように選ぶことができることを示せ． 解答： I={1,2,...,2n-1}， Kj：第j日における勝ちチームからなる集合 Mj：第j日における負けチームからなる集合　とする． J⊆Iに対して，KJ=∪j∊J Kj とする（ KJ はJの日程内で少なくとも1勝したチームからなる集合となる）． Iを片方の部集合，2n個のチームをもう片方の部集合とし， 各i∊Iに対して，iとKiに属する頂点達とを全て辺で結ぶことで構成される2部グラフを考えると， 問題を示すには，ホールの結婚定理より， 任意のJ⊆Iに対して，|KJ|≧　①　が成立することを示せばよい． あるJ⊆Iに対して，|KJ|≦　①　-1と仮定する． MJ=∩ j∊J Mj とする（ MJ はJの日程内で　　　　　②　　　　　チームからなる集合となる）． このとき，|KJ|+|MJ|=　③　となる．・・・（＊） 　　　　　　　　　　　　　　　　　　　④　　　　　　　　　　　　　　　　　　　　ので， x∊ MJとすると，xはJの日程内でMJ-{ x }に属するチームと試合を行わない． よって，|MJ-{ x }|≦　　　　⑤　　　　となるので，　　　　　　 　 ⑥　 　　　　　　　　となり（＊）に矛盾． よって，任意のJ⊆Iに対して，|KJ|≧　①　が成立する．

2 2017年度 有限幾何学 期末試験 問2 Gを橋を持たない連結グラフとし，w∊V(G)を始点としてGに対してDFSを実行したものとし，Tをwを根とするDFS木とする． DFS木と授業で扱ったDFSを用いた強連結な向き付けを与えるアルゴリズム（ロバーツのアルゴリズム）に関して， 　　 次の各問に答えよ． DFS木の構成法より，Gの辺uvに対してuとvはTにおいて ① と ② （または ② と ① ）の関係であることが分かる． ①と②に入る用語（用語を忘れた場合はuとvの位置関係の厳密な説明）を書け． (2)　以下の文章はロバーツのアルゴリズムによって得られる向き付けが強連結であることの説明である． 　　 この文章を読み，各問に答えよ． ロバーツのアルゴリズムによって得られる向き付けが強連結であることを示すには Tの ③ からwへのGにおける有向道が存在することを示せばよい．　　　 v1をTの ③ とし， v1－をv1の親とする．wとv1－を結ぶT上の道をP0とする． Gは　　　　④　　　　なので，(1)よりv1とP0の間にE(G)-E(T)に属す辺v1u1が存在することが分かる． u1－をu1の親とする．wとu1－を結ぶT上の道をP1とし，u1とv1を結ぶT上の道をQ1とする． Gは　　　　④　　　　なので，(1)よりP1とQ1の間にE(G)-E(T)に属す辺u2v2が存在することが分かる (ただし，u2∊V(P1)，v2∊V(Q1)とする)． このような辺u2v2をu2とwのTにおける距離ができる限り近くなるように選ぶ． u2－をu2の親とする．wとu2－を結ぶT上の道をP2とし，u2とu1－を結ぶT上の道をQ2とする． Gは　　　　④　　　　なので，(1)よりP2とQ2の間にE(G)-E(T)に属す辺u3v3が存在することが分かる (ただし，u3∊V(P2)，v3∊V(Q2)とする)． 以下同様にして，u4，v4，u5，v5...を選んでいく． 　　　　　　　⑤　　　　　　なので，ある自然数nに対してun=wとなる． 以上より，次の図のようなv1からwへの有向道が存在することが分かる（図ではn=4としている）． w=u4 u3 v4 u2 v3 u1 v2 v1 (2)-(i)　③に当てはまる用語を書け． (2)-(ii)　④と⑤に当てはまる文章を書け． (2)-(iii)　辺v2u2をu2とwのTにおける距離ができる限り近くなるように選んだ理由を書け． (2)-(iv)　図にv1からwへの有向道を書き込み証明を完成させよ．