スライド 1

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

Download Report