2016 年度情報数学期末試験問題 (その 1)

2016 年度情報数学期末試験問題 (その 1)
2016.8.4
問題 1. 図 1 に示す単純グラフ 0∼14 について，以下の文章の空欄を埋める番号または数を答えよ．
• 以下の隣接行列 A を持つグラフはグラフ
である．
(1)

0
0

1
A=
0

0
1
0
0
0
1
0
1
1
0
0
1
1
1
0
1
1
0
1
1
0
0
1
1
0
0

1
1

1

1

0
0
正解: 4
• グラフ
は完全グラフである．正解: 2
(2)
• 正則グラフは完全グラフであるグラフ (2) を含めて
• グラフ
個ある．正解: 4(グラフ 2, 5, 8, 13)
(3)
(4)
とグラフ
は同型である．（番号の小さい方を (4) に答えること）正解: 0,
• グラフ
(6)
はグラフ 1 の補グラフである．正解: 7
• グラフ
(7)
は自己補グラフである．正解: 5
(5)
6
• 2 部グラフは
個あり，特にグラフ
(8)
は完全 2 部グラフである．正解: 4(グラフ 3,
(9)
10, 11, 12), 3
• オイラーグラフは
(10)
個ある．正解: 7(グラフ 0, 1, 2, 4, 5, 6, 13)
• 橋を持つグラフは
(11)
個，切断点を持つグラフは
個ある. 正解: 3(グラフ 7, 9, 10),
(12)
7(グラフ 0, 1, 6, 7, 9, 10, 14)
• グラフ 10 において，直径は
節点 h への順路は
であり，節点 e の次数は
(13)
である．また，節点 c から
(14)
通り，小道は 1 (16) 通りある．正解: 5(c と g の距離 5), 4, 6, 4(小道
(15)
の数は 14)
a
a
b
a
e
f
b
b
d
c
a
c
f
e
d
e
䉫䊤䊐0
c
e
d
䉫䊤䊐1
䉫䊤䊐2
a
f
d
䉫䊤䊐3
䉫䊤䊐4
e
f
䉫䊤䊐6
b
a
e
a
b
f
c
䉫䊤䊐7
c
a
e
b
b
b
g
䉫䊤䊐5
a
e
c
e
d
b
d
c
b
c
f
a
d
f
e
a
a
b
c
b
d
g
a
d
c
䉫䊤䊐8
b
a
d
c
䉫䊤䊐9
a
b
b
d
c
f
e
d
g
h
䉫䊤䊐10
i
c
d
e
g
h
䉫䊤䊐11
f
c
d
e
f
䉫䊤䊐12
図1
c
d
e
䉫䊤䊐13
f
e
f
䉫䊤䊐14
問題 2 図 2 について以下の文章の空欄を埋める番号または数を答えよ．
• この木の高さは
(17)
であり， 1 (18) 個の葉を持っている．正解: 4, 3(葉の数は 13)
• 節点 c の次数は
(19)
である．正解: 4
• 節点 k は
個の兄弟節点を持つ．正解: 3
(20)
• 自分自身を自分自身の祖先，子孫とみなす場合で，節点 f は
(21)
個の祖先と
(22)
孫を持つ．また，図 2 を順序木としてみた場合，f より上位の節点は，f 自身を含めて
個の子
(23)
個
ある．正解: 3, 7, 7
a
b
c
d
e
f
m
g
h
i
j
k
t
u
l
n
o
v
q
p
w
r
s
y
x
図2
問題 3. 以下の式で表される {1, 2, 3} × {1, 2, 3} 上の関係が，同値関係，半順序関係，全順序関係か，いず
れでもない場合どの性質を持つか選択肢中から選べ．
㩿㪉㪏㪀
(24) {((x1 , y1 ), (x2 , y2 )) | x1 + y1 ≤ x2 + y2 }
(25) {((x1 , y1 ), (x2 , y2 )) | x1 ≤ x2 ∧ y1 ≤ y2 }
(26) {((x1 , y1 ), (x2 , y2 )) | x1 < x2 ∧ y1 < y2 }
(27) {((x1 , y1 ), (x2 , y2 )) | x1 < x2 ∨ (x1 = x2 ∧ y1 ≤ y2 )}
選択肢
(1,3)
(2,3)
(3,3)
(1,2)
(2,2)
(3,2)
(1,1)
(2,1)
(3,1)
0:同値関係
1:半順序関係
2:全順序関係
3:反射律と対称律を満たす
4:推移律と反射律を満たす
5:推移律と反対称律を満たす
6:対称律のみ満たす
7:推移律のみ満たす
正解:(24) 4, (25) 1, (26) 5, (27) 2, (28) 0
8:それ以外
問題 4. 以下の 2 項関係、グラフ理論の用語に関する日本語と英語の組合せのうち，適切でないものを (29)
∼(30) それぞれの中から一つずつ選びなさい．
(29)
0: 反射律 symmetric law
1: 推移律 transitive law
2: 半順序関係 partial order relation
3: 同値関係 equivalence relation
4: 補グラフ complement graph
5: 完全グラフ complete graph
6: 正則グラフ regular graph
7: 2 部グラプ bipartite graph
正解: 0 (正しくは reflexive law)
(30)
0: 径路 walk
1: 小道 trail
2: 順路 path
3: 閉路 cycle
4: 根 route
5: 葉 leaf
6: 親 parent
7: 子 child
正解: 4(正しくは root)
2016 年度情報数学期末試験問題 (その 2)
裏面はその 1 のメモ用紙として使用してよい
問題 5. 以下の条件を満たす単純無向グラフまたは木を描け．節点にラベ
ルを付けなくてよい．(20 点)
(1) 完全グラフ K3
(2) 完全 2 部グラフ K5,2
(3) 節点数 5，直径 2 の無向木
(4) 7 つの節点と 8∼9 本の辺から構成されるオイラーグラフを同型で
ないものをなるべく多く列挙せよ．
(5) 7 つの節点からなる正則 2 分木のうち、順序木としてみた場合同型
でないものをなるべく多く列挙せよ．
問題 6. 以下の問いに答えよ．(20 点)
(1) 次の構文木のリスト表現を書け
(
)
$
!
"
#
$
&
%
'
正解：(+, (−, (÷, x, 2), 1), (×, (−, 9, 4), z))
(2) 順序集合 (X; ≤) とその部分集合 A における A の上界と A の上
限の関係について簡潔に説明せよ（上界そのものの説明は不要）
A の上界に最小要素が存在する場合，その最小要素が上限
(3) グラフ G = (V, E) の部分グラフ G0 = (V 0 , E 0 ) について V 0 , E 0
の満たすべき条件を集合の包含関係を用いて簡潔に示せ
V 0 ⊆ V , E 0 ⊆ E, E 0 ⊆ V 0 × V 0
(4) 無向木について簡潔に説明せよ
連結かつ無閉路のグラフ
(5) ハミルトングラフについて簡潔に説明せよ
全ての節点を一度ずつ通る閉路を持つグラフ

Download Report