2015 年度 有限幾何学 期末試験 次の各問に答えよ．（ (1), (2), (3), (4), (5), (7), (8), (10) は答えだけでよい） (1) 有向閉路が存在しない位数 4 のトーナメントを描け． (2) 内点の個数が 10 個の正則 2 分木の葉の個数を求めよ． (3) グラフ G が強連結な向き付け可能であるための（授業で紹介した）必要十分条件を書け． (4) 授業で紹介したオイラーの公式を書け． (5) 次のグラフの染色数をそれぞれ求めよ． ( ただし， m,n ≧ 3 とする ) (i) K n (ii) K m,n (iii) 位数 n の閉路 (iv) 位数 n の道 (v) 位数 n の木 (6) T を k 個の辺をもつ木， G を δ(G) ≧ k の単純グラフとする．このとき G は T を部分グラフとして含むことを示せ． （ δ(G) は G の最小次数） ヒント： k に関する帰納法 (7) K 3,3 の厚さと交差数を求めよ． (8) 重み 1 ， 3 ， 5 ， 7 ， 8 に対するハフマン木を描け． また，対応するハフマンコードを答えよ（描いたハフマン木の各葉の下に符号語を書け）． (9) 位数 3 以上の極大平面的グラフ G に対して， |E(G)|=3|V(G)|-6 が成り立つことを示せ． (10) 次のグラフの最小全域木をクルスカルのアルゴリズムを適用して求めよ．また，その重さも答えよ． 2 b f c a d e g h
2015 年度 有限幾何学 期末試験略解 次の各問に答えよ．（ (1), (2), (3), (4), (5), (7), (8), (10) は答えだけでよい） (1) 有向閉路が存在しない位数 4 のトーナメントを描け． 例 (2) 内点の個数が 10 個の正則 2 分木の葉の個数を求めよ． 11 個 (5) 次のグラフの染色数をそれぞれ求めよ． ( ただし， m,n ≧ 3 とする ) (i) K n (ii) K m,n (iii) 位数 n の閉路 (iv) 位数 n の道 (v) 位数 n の木 n 2 n が偶数： 2 ， n が奇数： (6) T を k 個の辺をもつ木， G を δ(G) ≧ k の単純グラフとする．このとき G は T を部分グラフとして含むことを示せ． ヒント： k に関する帰納法 略証： k=1 の場合は明らか． T を k 個の辺をもつ木とし， x を T の葉， y を x に隣接する頂点とする． T’=T-x とする． このとき， T’ は k-1 個の辺をもつ木であり，また， δ(G) ≧ k ≧ k-1 なので帰納法の仮定より， G は T’ を含む． |V(T’)|=|V(T)|-1=|E(T)|=k なので， δ(G) ≧ k より， y は G 内において V(T’) の要素以外の頂点 x’ と隣接する． T’ に頂点 x’ と辺 yx’ を加えたグラフが T と同型な G の部分グラフとなる． (7) K 3,3 の厚さと交差数を求めよ．厚さ２，交差数 1 (8) 重み 1 ， 3 ， 5 ， 7 ， 8 に対するハフマン木を描け． また，対応するハフマンコードを答えよ（描いたハフマン木の各葉の下に符号語を書け）．
2015 年度 有限幾何学 期末試験略解 (9) 位数 3 以上の極大平面的グラフ G に対して， |E(G)|=3|V(G)|-6 が成り立つことを示せ． 略証： G の頂点数を p, 辺数を q, 領域数を r とする． オイラーの公式より， p-q+r=2 ． 各領域の境界線上の辺の数は 3 なので， 3r=2q 以上より， 3p-3q+2q=6, ∴ q=3p-6 となる． (10) 次のグラフの最小全域木をクルスカルのアルゴリズムを適用して求めよ．また，その重さも答えよ． 2 重さ： 35 b f c a d e g h