神戸大学 システム情報学研究科 2017年8月実施 専門科目 システム理論 [1]

Author

祭音Myyura

Description

~ の各地点の間に光ファイバーを設置してインターネットで相互につながるようにしたい。 ただし、2つの地点の間で直接つながるか、他地点を経由してつながるかは問わないとする。 図 (a) に示されたグラフは、各点 (vertex) が地点 ~ のいずれかに対応し、各辺 (edge) がその両端に対応する 2 地点間に光ファイバーが設置可能であることを示す (辺のない 2 地点間は地理的な条件などにより光ファイバーが設置できないことを示す)。

以下の設問に答えよ。

図 (a)

(1) 図 (a) に示されたグラフについて、隣接行列 (adjacency matrix) およびラプラシアン行列 (Laplacian matrix) を示せ。

(2) 図 (a) に示されたグラフの全域木 (spanning tree) は、 ~ の各々を一度だけ通り、かつ、閉路 (cycle) のないような連結した光ファイバー網に対応する。このとき、全域木の辺の数はいくつか示せ。また、全域木が何通りあるか示せ。ただし、根拠も示せ。

(3) 表 (b) は、光ファイバーが設置可能な 2 地点間についてそれぞれの設置費用を 1000 万円を単位として示したものである。前問 (2) の全域木のうち、光ファイバーの設置に係る総費用が最小となる場合について、その総費用を示せ。

	A	B	C	D	E
A	-	1	-	-	4
B		-	2	7	3
C			-	8	5
D				-	6
E					-

表 (b)

Kai

(1)

隣接行列

次数行列

ラプラシアン行列

(2)

行列木定理より、 の 余因子 は

であるので、図 (a) に示されたグラフの全域木の個数も 40 である。

(3)

最小木

最小総費用は 12 である。