2012年度有限幾何学期末試験解答各10点 (2),(4),(5),(6)は提出課題解答を参照 (1) 頂点数と辺の数が等しい連結グラフが丁度一つの閉路を持つことを示せ． (1)の解答：グラフGを|V(G)|=|E(G)|である連結グラフとする． Gは連結グラフなので全域木Tを含む． Tは木なので閉路を持たず，辺を追加すると丁度一つの閉路ができる．またTが木であることより，|E(G)|=|V(G)|=|V(T)|=|E(T)|+1となり， GはTに辺を一つ追加したグラフであることが分かる．以上よりGが丁度一つの閉路を持つことが分かる． (3) 強連結なトーナメントが長さ3の有向閉路を持つことを示せ． (3)の解答：グラフGを強連結なトーナメントとする． v∈V(G), A:={w∈V(G) : 辺vwはvからwへ向き付けされている}, B:={w∈V(G) : 辺wvはwからvへ向き付けされている} とする． A=∅と仮定すると，vからB内の任意の頂点への有向道が存在しないのでGが強連結であることに矛盾．よって，A≠∅．同様にしてB≠∅が成立． A内の頂点とB内の頂点を結ぶ辺が全てBからAの向きに向き付けされていると仮定すると， A内の任意の頂点からB内の任意の頂点への有向道が存在しないのでGが強連結であることに矛盾．よって，あるa∈Aとあるb∈Bに対し，辺abはaからbへ向き付けされている．よってGは長さ3の有向閉路bvabを持つ． (7) 図1のグラフの最小全域木を描き，その重さも答えよ． (7)の解答： b 7 9 5 7 f 6 12 16 c a 21 9 g 8 14 3 d h 7 9 2 e 重さ 40 2012年度有限幾何学期末試験解答 (8) 重み 1，3，5，7，8 に対する総コード長が最小の2分木を描き，その総コード長も答えよ． (8)の解答： 1 3 5 7 8 総コード長 = 1×3＋3×3＋5×2＋7×2＋8×2 = 52 (9) 図2のグラフはK3,3の細分を部分グラフとして含む．このグラフを図示せよ． (9)の解答： a b c e d f g (10) 図2のグラフの交差数を求めよ．（理由も書くこと） (10)の解答：(9)より図2のグラフは平面的ではない．よって図2のグラフの交差数は1以上．また，図2のグラフは右図のように平面上に描けるので図2のグラフの交差数は1以下．よって図2のグラフの交差数は1である． a b c e d f g