有限幾何学　 　　　　　　第13回.

Presentation on theme: "　　　　有限幾何学　 　　　　　　第13回."— Presentation transcript:

1 　　　　有限幾何学　 　　　　　　第13回

2 提出課題8の問5 有向グラフGに対して，全ての頂点を含む有向道が存在するとき， Gは半ハミルトンであるという．
全てのトーナメントは半ハミルトンであることを示せ． トーナメント：向き付けされた完全グラフ

3 提出課題8の問5の解答 頂点数nに関する帰納法で証明する． n=1のときは自明 n<kのときに命題が正しいと仮定し，

4 提出課題8の問5の解答 Gを位数kのトーナメントとし，v∊V(G)とする． G-vは位数がk-1のトーナメントなので， 帰納法の仮定より，
　　全ての頂点を含む有向道 v1v2...vk-2vk-1 が存在する （各1≦i≦k-2に対して辺vivi+1はviからvi+1に向き付けされている）

5 提出課題8の問5の解答 Gにおいて辺vv1がvからv1に向き付けされていると，
vv1v2...vk-2vk-1がGにおける全ての頂点を含む有向道となる． よって ①　Gにおいて辺vv1がv1からvに向き付けされているとしてよい． また， Gにおいて辺vvk-1がvk-1からvに向き付けされていると， v1v2...vk-2vk-1vがGにおける全ての頂点を含む有向道となる． ②　Gにおいて辺vvk-1がvからvk-1に向き付けされているとしてよい．　　　

6 提出課題8の問5の解答 ①と②より， 1≦∃i ≦k-2 s.t. 辺vviはviからvに向き付けされている かつ
辺vvi+1はvからvi+1に向き付けされている このとき， v1v2...vivvi+1 …vk-2vk-1v がGにおける全ての頂点を含む有向道となる．

7 提出課題10の問2 Gを多面体とし，全ての面は五角形または六角形であるとする． このとき，Gには12個以上の五角形の面があることを示せ．

8 提出課題10の問2の解答 五角形をx個，六角形をy個とする． このとき， |E(G)| = (5x + 6y)/2．
よって，オイラーの公式より， |V(G)|- (5x + 6y)/2 + (x+y) =2 ∴ |V(G)| = 2 + 3x/2 + 2y また，多面体の各頂点が3つ以上の面の共有点であることから 各頂点の次数が3以上であることが分かるので，握手補題より， 5x+6y=2|E(G)|=Σd(v)≧3|V(G)|=6+9x/2+6y ∴ x≧12

9 提出課題10の問3 サッカーボールは，正5角形と正6角形を それぞれ何枚かずつ下図のように貼り合わせて作られている．
正5角形と正6角形の枚数はそれぞれ何枚か．

10 提出課題10の問3の解答 五角形をx個，六角形をy個とする． 各頂点の次数が3なので， 問2の解答における不等号が等号となるので x=3
また，各頂点に対して， 1つの正5角形と2つの正6角形が隣接しているので 頂点数は5x=3y． ∴ y=5

11 提出課題11の問2 橋がない連結グラフ（地図と呼ぶ）が隣接している２つの面が 同じ色にならないようにk色で面を彩色できるとき， 地図はk-面彩色可能であるという． 地図Gが2-面彩色可能であるための必要十分条件が Gがオイラーグラフであることを証明せよ．

12 提出課題11の問2の解答 「2-面彩色可能⇒オイラーグラフ」の証明： 2-面彩色可能⇒ Gの隣接している２つの面を同じ色にならないように 2色で面を彩色することができる⇒ Gの各頂点の周りには色が交互に偶数回現れる⇒ Gの各頂点の次数は偶数⇒ Gはオイラーグラフ

13 提出課題11の問2の解答 「オイラーグラフ⇒2-面彩色可能」の証明： Gをオイラーグラフとする． Gの各領域を頂点とし，隣接する領域どうしを 辺で結ぶことによって得られるグラフをHとする このとき， 「Gが2面彩色可能 ⇔Hが2彩色可能⇔Hが2部グラフ⇔Hが奇閉路を持たない」より， Hの任意の閉路が遇閉路であることを示せばよい．

14 提出課題11の問2の解答 「オイラーグラフ⇒2-面彩色可能」の証明： CをHの任意の閉路とする． このとき､ Cの頂点数＝Cと交差するGの辺の数 また， 「Gがオイラーグラフ⇔Gは辺素な閉路D1,D2,…,Drに分割できる」より， Cの頂点数＝Σ（Cと交差するDiの辺の数）=∑偶数=偶数 ∴Cは遇閉路 ∴ Hの任意の閉路は遇閉路である

15 提出課題12の問3 Bは男性の集合とし，Bの各男性は2人以上の 恋人と結婚したいとする． この問題に解があるための必要十分条件を見つけよ．

16 提出課題12の問3の解答 2部グラフG(V1,V2)に置き換えて考える．（V1が男性の集合） x∊V1, y,z∊V2 xy,xz∊E(G(V1,V2))の形の G(V1,V2)の部分グラフ全体からなる集合をS(G)とおく． 次の集合M⊆S(G)が存在するための 必要十分条件を求める問題に置き換えることができる． ∀X,∀Y∊M, X∩Y=∅ かつ ∀x∊V1 ∃X∊M s.t. x∊V(X)

17 提出課題12の問3の解答 次の定理を証明する． 定理 2部グラフG(V1,V2)に対し， ⇒の証明は簡単なので省略
∃M⊆S(G) s.t. （∀X,∀Y∊M, X∩Y=∅　かつ　∀v∊V1 ∃X∊M s.t. v∊V(X)）」 ⇔ 「V1の任意の部分集合Aに対して，|NG(A)|≧2|A|」 ⇒の証明は簡単なので省略

18 提出課題12の問3の解答 ⇒ ⇐の証明：まずは，V1の各頂点を2個の独立点に分ける． （u∊V1に対して，そのコピーをu’と書くことにする）
G G’ u' u u ⇒ v v v' V1 V2 V1’ V2’

19 提出課題12の問3の解答 ⇐の証明： G’においてV1’の頂点を全て飽和するマッチングが存在すると， G G’ u' u u v v v'

20 提出課題12の問3の解答 ⇐ ⇐の証明： Gにおいて所望のMが存在することが分かる． G G’ u' u u v v v' V1 V2

21 提出課題12の問3の解答 ⇐ ⇐の証明： よって，G’において V1’の頂点を全て飽和するマッチングが存在することを示せばよい． G G’
u' u u ⇐ v v v' V1 V2 V1’ V2’

22 提出課題12の問3の解答 ⇐の証明： A’⊆V1’とし， A={ v∊V1 : v∊ V1’ または v’∊V1’} とする． このとき， |NG’(A’)| = |NG(A)| ≧ 2|A| ≧ |A’| よって，ホールの結婚定理より， G’において V1’の頂点を全て飽和するマッチングが存在する．

23 提出課題13（今日の課題） 問1： ある国には都市が100あり，都市のいくつかは航空路で 結ばれている．どの都市からも別の都市へ行けることは 分かっている（中間の空港を経由する場合もある）． どこの都市からスタートしても 全ての都市を197フライト以下で訪れることができることを示せ． ヒント：全域木に沿って・・・

24 提出課題13（今日の課題） 問2： 位数11の完全グラフのそれぞれの辺が 赤または青に塗られている． このグラフから赤の辺だけからなるグラフ， 青の辺だけからなるグラフを取り出す． この二つのグラフのうち少なくとも1つは 平面的グラフではないことを示せ． ヒント：オイラーの公式の系1(1) 平面的グラフGに対し，|E(G)|≦3|V(G)|-6

25 提出課題13（今日の課題） 問3： ある国の全ての町はほかの全ての町と 一方通行の道路で結ばれてる． このとき， 全ての町へ行けるような町が少なくとも1つあることを示せ． ヒント： トーナメントに向き付けされた根付き木 （根から葉に向かって向き付けされている）が存在することを 頂点数に関する帰納法で示す．

26 提出課題13（今日の課題） 問4： どんなトーナメントも長さ（辺の数）が高々２の有向道によって 他の任意の点に到達可能な１点を含む． ヒント：帰納法． 頂点vとNG+(v)を取り除いて考える．

27 提出課題13（今日の課題） 問5：内部のどの二点間も， 外部を通らない直線でつなげる多面体を凸多面体という． 正多面体とは全ての面が同一の正多角形で， どの頂点にも同じ数の面が集まっている凸多面体である． 全ての面が正方形の正多面体は立方体だけであることを示せ． ヒント：4×面の数=2×辺の数，各頂点の次数＝・・・ 握手補題，オイラーの定理(p-q+r=2) 類題：全ての面が正5角形の場合の面の数は？

28 期末試験について A4用紙1枚に自筆で書き込んだ（両面）ものを持ち込み可とする． 試験時間は60分 公式を書かせるような問題は出さない
今日の提出課題から文章を変えて1問， 今日の提出課題から同じような問題を1問出す 過去問から同じかほぼ同じ問題を数問出す その他から数問出す

29 やむを得ない理由で試験を受けれない場合 教育実習で中間試験を受けることができなかった 何かの大会で期末試験を受けることができない
等の理由で中間試験か期末試験どちらかを 受けることができなかったまたはできない場合は， 今日の提出課題をレポートとします． レポートは1つのPDFファイルでメールで送ってください （作成はtex,word等なんでも構いません）． 締め切りは来週の金曜日の午前7時30分とします．