図2 x11 図1 x6 x10 x12 x3 x5 x7 x9 x13 x2 x4 x8 x14 (0,0) (1,0) x1 x15 2019年度 有限幾何学 中間試験 問1　次の問題とその解答を読み，各問に答えよ． Mountain climbing problem f:[0,1]→Rを，f(0)=0，f(1)=0，0<x<1においてはf(x)>0である折れ線グラフとする（例：図1）． AliceとBobはこのグラフ上をそれぞれ(0,0)と(1,0)から出発し，同じ高度を保って移動するものとする． このとき，AliceとBobは出会うことが可能であることを示せ． 解答： 折れ線グラフには平らなところがないとしてよい． 全ての極値点に対して，その点を通るx軸と平行な直線を引き， y=f(x)との交点を左から順にx1,x2, ..., xn とおく（注意：x1=(0,0)，xn=(1,0)）（例：図1のfに対しては図2のようになる）． 便宜上，(0,0)と(1,1)以外の極小，極大となる点をそれぞれ谷，峰と呼ぶことにする． このとき，以下のように単純グラフGfを定義する． V(Gf)={ (xi,xj) : 「1≦i≦j≦n」 かつ 「xiまたはxjは谷または峰である」 }∪{(x1,xn) }， (a,b),(c,d)∊V(Gf)に対して， (a,b)(c,d)∊E(Gf) ⇔ AliceとBobがaとbからそれぞれ出発したときに， 同じ高度を保ちつつ，上り続けるか下り続けることでそれぞれcとdに到達できる． （例：図1のfに対しては例えば，(x1,x15)(x3,x13), (x3,x13)(x4,x14)∊ E(Gf) ） このとき(X,Y)∊V(Gf)に対して， X＝x1，Y=xnのとき， (X,Y)の次数は　①　 ， 「Xが谷，Yが谷」または「Xが峰，Yが峰」Aのとき， (X,Y)の次数は　②　 ， 「Xが谷，Yが峰」または「Xが峰，Yが谷」 Bのとき， (X,Y)の次数は　③　 ， XとYのいずれか片方が谷で峰でもないCとき， (X,Y)の次数は　④　 ， X=Y Dのとき， (X,Y)の次数は　⑤　 ． よって，X＝x1，Y=xnのとき， (X,Y)の次数は　①　であることから， (x1,xn)を含むGfの成分に対して握手補題から得られる性質Eを適用することで (x1,xn)を含むGfの成分に　⑥　である点が存在することが分かる． 以上より，AliceとBobは出会うことが可能であることが分かる．□ 右の図3で表されるfに対して，グラフGfの頂点数と辺数を求めよ．（10点） ①から⑤の空欄に当てはまる数字をそれぞれ求めよ．（各5点　計25点） 下線部Eの性質がどのような性質であるかを述べよ．（5点） ⑥に当てはまる文章をA，B，C，Dの中から選べ．（5点） 図2 x11 図1 x6 x10 x12 x3 x5 x7 x9 x13 x2 x4 x8 x14 (0,0) (1,0) x1 x15 図3

図4：Pの描き方 x z- z y 問2 次の定義，定理と定理の証明を読み，各問に答えよ． 定義：部集合がXとYである2部グラフGに対して， 問2　次の定義，定理と定理の証明を読み，各問に答えよ． 定義：部集合がXとYである2部グラフGに対して， σ1,1(G)=min{ dG(x)+dG(y) : x∊X，y∊Y，xy∉E(G) }とする（ただし完全2部グラフに対しては値を∞とする）． 定理（Moon and Moser 1963） Gを部集合がXとYである2部グラフとし，|X|=|Y|=nであるとする（n≧2）． このとき､σ1,1(G)≧|X|+1ならばGはハミルトン閉路を持つ． 証明 あるnに対して定理が成り立たないと仮定し， Gを|X|=|Y|=nで定理の仮定を満たすが ハミルトン閉路を持たない2部グラフの中で辺集合が極大であるものとする． x∊X，y∊YをGの非隣接2頂点とする． このとき，xとyを結ぶGの全ての頂点を含む道Pが存在する．A 以下，図4のようにPを描いて考える． Gの頂点zに対して，P上でzの左隣にある頂点をz-と書くことにする． NP(y)=NG(y)∩V(P)，NP(x)-={ z- : z∊NG(x)∩V(P) }と定義する． このとき，Gは　①　のでNP(x)- ∩ NP(y) =∅となる． よって，dG(x)+dG(y)≦|X|Bとなるので，　②　となり矛盾． よって，定理が成立することが分かる．□ この定理はσ1,1(G)≧|X|+1の下限を|X|に改良することができない．n=4の場合にこのことが分かる例を描け．（10点） 下線部Aが成立する理由を述べよ．（5点） 下線部①に当てはまる文章を証明の文章中から抜き出して書け．（5点） 下線部Bの不等式が成立する理由を述べよ．（10点） 下線部②に当てはまる文章を書け．（5点） 問3 全ての頂点の次数が偶数である連結グラフをオイラーグラフといい， オイラーグラフを全域部分グラフとして持つグラフを超オイラーグラフという． nを5以上の奇数とする． 次の2つの性質を持つ位数nの連結2部グラフGで超オイラーグラフではないものを1つ見つけ，その概形を描け．（20点） 性質①：Gの全ての辺xyに対して，dG(x)+dG(y)≧n 性質②：Gの最小次数は2以上 （注意：一般のnに対するグラフの概形を描くこと） 図4：Pの描き方 x z- z y

図2 x11 図1 x6 x10 x12 x3 x5 x7 x9 x13 x2 x4 x8 x14 (0,0) (1,0) x1 x15 2019年度 有限幾何学 中間試験解答 問1　次の問題とその解答を読み，各問に答えよ． Mountain climbing problem f:[0,1]→Rを，f(0)=0，f(1)=0，0<x<1においてはf(x)>0である折れ線グラフとする（例：図1）． AliceとBobはこのグラフ上をそれぞれ(0,0)と(1,0)から出発し，同じ高度を保って移動するものとする． このとき，AliceとBobは出会うことが可能であることを示せ． 解答： 折れ線グラフには平らなところがないとしてよい． 全ての極値点に対して，その点を通るx軸と平行な直線を引き， y=f(x)との交点を左から順にx1,x2, ..., xn とおく（注意：x1=(0,0)，xn=(1,0)）（例：図1のfに対しては図2のようになる）． 便宜上，(0,0)と(1,1)以外の極小，極大となる点をそれぞれ谷，峰と呼ぶことにする． このとき，以下のように単純グラフGfを定義する． V(Gf)={ (xi,xj) : 「1≦i≦j≦n」 かつ 「xiまたはxjは谷または峰である」 }∪ { (x1,xn) } ， (a,b),(c,d)∊V(Gf)に対して， (a,b)(c,d)∊E(Gf) ⇔ AliceとBobがaとbからそれぞれ出発したときに， 同じ高度を保ちつつ，上り続けるか下り続けることでそれぞれcとdに到達できる． （例：図1のfに対しては例えば，(x1,x15)(x3,x13), (x3,x13)(x4,x14)∊ E(Gf) ） このとき(X,Y)∊V(Gf)に対して， X＝x1，Y=xnのとき， (X,Y)の次数は　1　 ， 「Xが谷，Yが谷」または「Xが峰，Yが峰」Aのとき， (X,Y)の次数は　4　 ， 「Xが谷，Yが峰」または「Xが峰，Yが谷」 Bのとき， (X,Y)の次数は　0　 ， XとYのいずれか片方が谷でも峰でもないCとき， (X,Y)の次数は　2　 ， X=Y Dのとき， (X,Y)の次数は　（1または）2または3　 ． よって，X＝x1，Y=xnのとき， (X,Y)の次数は　1　であることから， (x1,xn)を含むGfの成分に対して握手補題から得られる性質Eを適用することで (x1,xn)を含むGfの成分に　X=Y　である点が存在することが分かる． 以上より，AliceとBobは出会うことが可能であることが分かる．□ 右の図3で表されるfに対して，グラフGfの頂点数と辺数を求めよ．（10点） ①から⑤の空欄に当てはまる数字をそれぞれ求めよ． （各5点　計25点） 下線部Eの性質がどのような性質であるかを述べよ．（5点） ⑥に当てはまる文章をA，B，C，Dの中から選べ．（5点） (1)　頂点数8，辺数8 (3)　奇点の個数は偶数個である 図2 x11 図1 x6 x10 x12 x3 x5 x7 x9 x13 x2 x4 x8 x14 (0,0) (1,0) x1 x15 図3

図4：Pの描き方 x z- z y 問2 次の定義，定理と定理の証明を読み，各問に答えよ． 定義：部集合がXとYである2部グラフGに対して， 問2　次の定義，定理と定理の証明を読み，各問に答えよ． 定義：部集合がXとYである2部グラフGに対して， σ1,1(G)=min{ dG(x)+dG(y) : x∊X，y∊Y，xy∉E(G) }とする（ただし完全2部グラフに対しては値を∞とする）． 定理（Moon and Moser 1963） Gを部集合がXとYである2部グラフとし，|X|=|Y|=nであるとする（n≧2）． このとき､σ1,1(G)≧|X|+1ならばGはハミルトン閉路を持つ． 証明 あるnに対して定理が成り立たないと仮定し， Gを|X|=|Y|=nで定理の仮定を満たすが ハミルトン閉路を持たない2部グラフの中で辺集合が極大であるものとする． x∊X，y∊YをGの非隣接2頂点とする． このとき，xとyを結ぶGの全ての頂点を含む道Pが存在する．A 以下，図4のようにPを描いて考える． Gの頂点zに対して，P上でzの左隣にある頂点をz-と書くことにする． NP(y)=NG(y)∩V(P)，NP(x)-={ z- : z∊NG(x)∩V(P) }と定義する． このとき，Gは　①　のでNP(x)- ∩ NP(y) =∅となる． よって，dG(x)+dG(y)≦|X|Bとなるので，　②　となり矛盾． よって，定理が成立することが分かる．□ この定理はσ1,1(G)≧|X|+1の下限を|X|に改良することができない．n=4の場合にこのことが分かる例を描け．（10点） (2)　下線部Aが成立する理由を述べよ．（5点） 　　　Gはハミルトン閉路を持たないグラフの中で辺集合が極大であるものなので， 　　　Gに辺xyを追加したグラフはハミルトン閉路をもつ．このハミルトン閉路から辺xyを除くことで所望の道が得られる． (3)　下線部①に当てはまる文章を証明の文章中から抜き出して書け．（5点） 　　　ハミルトン閉路を持たない (4)　下線部Bの不等式が成立する理由を述べよ． （10点） dG(x)+dG(y)=|NP(x)|+|NP(y)|=|NP(x)-|+|NP(y) |=|NP(x)-∪NP(y)|≦|V(P)∩X|=|X| (5)　下線部②に当てはまる文章を書け．（5点） |X|+1≦σ1,1(G)≦|X| 問3 全ての頂点の次数が偶数である連結グラフをオイラーグラフといい， オイラーグラフを全域部分グラフとして持つグラフを超オイラーグラフという． nを5以上の奇数とする． 次の2つの性質を持つ位数nの連結2部グラフGで超オイラーグラフではないものを1つ見つけ，その概形を描け．（20点） 性質①：Gの全ての辺xyに対して，dG(x)+dG(y)≧n 性質②：Gの最小次数は2以上 （注意：一般のnに対するグラフの概形を描くこと） 略解：K2,n-2を描けばよい． 図4：Pの描き方 x z- z y

{(x1,x9)(x3,x7), (x2,x4)(x3,x3), (x2,x4)(x3,x5), (x4,x4)(x3,x3), 問1　(1)　 　x6 　x3 　x5 　x7 　x8 　x2 　x4 　x1 　x9 V(Gf)= {(x1,x9), (x2,x4), (x4,x4), (x4,x8), (x3,x3), (x3,x5), (x3,x7), (x6,x6)} E(Gf)= {(x1,x9)(x3,x7), (x2,x4)(x3,x3), (x2,x4)(x3,x5), (x4,x4)(x3,x3), (x4,x4)(x3,x5), (x4,x4)(x6,x6), (x4,x8)(x3,x7), (x4,x8)(x6,x6)}

問2　(4)　 上図より，NP(x)-∪NP(y)⊆V(P)∩X であることが分かる． dG(x)+dG(y)=|NP(x)|+|NP(y)| =|NP(x)-|+|NP(y) | =|NP(x)-∪NP(y)|　（∵ NP(x)-∩ NP(y) =∅ ） ≦|V(P)∩X| =|X| x ∊ y NP(x)- ∊X ∊Y x ∊ y NP(y)

K2,n-2が超オイラーグラフではないことは次のことから分かる． K2,n-2はオイラーグラフではない（n-2が奇数） 問3　 K2,n-2が超オイラーグラフではないことは次のことから分かる． K2,n-2はオイラーグラフではない（n-2が奇数） K2,n-2から連結性を保ったまま辺を除くと 次数1の点が現れるのでオイラーグラフではない この問では示す必要はないが，一般に k,m：整数（m≧k≧3）のとき，Km,nは超オイラーグラフとなる． ∵ 　　　m-kが偶数の場合　　　　　m-kが奇数の場合 …… …… …… …… …… 偶数の場合 と同様に 左側とつなぐ ……