慶應SFC　総合政策学部　情報入試　2018年　大問Ⅱ　過去問解説

(ア)

以上の法則を使って式を変形する。

なお

：常に真

：常に偽

である。

(イ)
S=(A)
から始めると
V={B,C,D,E,F,G,H}
Sと直接つながっている頂点を選ぶと
Vt={B,D,G}
距離が最小のBを選んで
S=(A-B)
Sと直接つながっている頂点を選ぶと
Vt={C,D,G}
距離がAから最小のDを選んで
S=(A-B,A-D)
すると
V={C,E,F,G,H}
になるのでSと直接つながっている頂点を選ぶと
Vt={C,E,F,G}
距離がAから最小のCを選んで
S=(A-B-C,A-D)
すると
V={E,F,G,H}
になるのでSと直接つながっている頂点を選ぶと
Vt={E,F,G,H}
距離がAから最小のGを選んで
S=(A-B-C,A-D,A-G)
すると
V={E,F,H}
になるのでSと直接つながっている頂点を選ぶと
Vt={E,F,H}
距離がAから最小のFを選んで
S=(A-B-C,A-D-F,A-G)
すると
V={E,H}
になるのでSと直接つながっている頂点を選ぶと
Vt={E,H}
距離がAから最小のHを選んで
S=(A-B-C-H,A-D-F,A-G)
残りのEを追加して
S=(A-B-C-H,A-D-F,A-G,A-D-E)
となる。

よって、付け加える頂点を順番に示すと
A,B,D,C,G,F,H,E

CがSに加わるときにCのほかにVtに含まれている頂点の数は3個。

Aからもっとも距離が離れている頂点はEで、その距離は10。

(ウ)
12 5 + 4 ×
は
(12+5)×4
であるから
68
である。

3 12 + 4 6 + ×
は
(3+12)×(4+6)
であるから
150
である。

(12+42)×21
は
12 42 + 21 ×
となり
36/(6+8)
は
36 6 8 + /
となる。