s a b f c e d 2016年度 有限幾何学 期末試験 問1：15点 有向グラフDとDの頂点vに対し，vからDのどの頂点へも長さ（辺の数）が高々２の有向道で到達できるとき， vをDのキング と呼ぶ．トーナメントがキングを持つことを示せ． 問2：各10点 次のグラフに対して， 各問に答えよ． ただし，同一の条件の点があればそれらの中のアルファベット順に選択すること (i) sを始点として深さ優先探索を行い，頂点のラベル付けをせよ． (ii) ロバーツのアルゴリズムを用いて強連結な向き付けを与えよ． 問3：（答えのみでよい）15点 内点の数が99個の正則2分木の子の数を求めよ． 問4：（答えのみでよい）15点 全ての面が5角形である正多面体の面の数を求めよ． 問5：（答えのみでよい）各5点 次のグラフの染色数をそれぞれ求めよ．(ただし，m,n≧3とする) (i) Kn (ii) Km,n (iii) 位数nの閉路 (iv) 位数nの木 問6：15点 2人のプレイヤーが交互に連結グラフGの異なる頂点v1,v2,…を隣接しているように選んでいき， 最後に頂点を選んだ方が勝ちとなるゲームを考える． Gが完全マッチングを持たないときに先手が必ず勝てることを示せ． ヒント：最大マッチング，増大道 a b s f c e d