跳到主要内容

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

标签：

Author​

祭音Myyura

Description​

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

以下の設問に答えよ。

図 (a)
​

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

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

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

ABCDE
A-1--4
B-273
C-85
D-6
E-

表 (b)
​

Kai​

(1)​

隣接行列 A\boldsymbol{A}

A=(0100110111010110110111110)\boldsymbol{A} = \begin{pmatrix} 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 1 \\ 0 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 0 \end{pmatrix}

次数行列 D\boldsymbol{D}

D=(2000004000003000003000004)\boldsymbol{D} = \begin{pmatrix} 2 & 0 & 0 & 0 & 0 \\ 0 & 4 & 0 & 0 & 0 \\ 0 & 0 & 3 & 0 & 0 \\ 0 & 0 & 0 & 3 & 0 \\ 0 & 0 & 0 & 0 & 4 \end{pmatrix}

ラプラシアン行列 L\boldsymbol{L}

L=D−A=(2−100−1−14−1−1−10−13−1−10−1−13−1−1−1−1−14)\boldsymbol{L} = \boldsymbol{D} - \boldsymbol{A} = \begin{pmatrix} 2 & -1 & 0 & 0 & -1 \\ -1 & 4 & -1 & -1 & -1 \\ 0 & -1 & 3 & -1 & -1 \\ 0 & -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & -1 & 4 \end{pmatrix}

(2)​

行列木定理より、L\boldsymbol{L} の 1111 余因子 Δ11\Delta_{11} は

Δ11=det(4−1−1−1−13−1−1−1−13−1−1−1−14)=40\Delta_{11} = \text{det} \begin{pmatrix} 4 & -1 & -1 & -1 \\ -1 & 3 & -1 & -1 \\ -1 & -1 & 3 & -1 \\ -1 & -1 & -1 & 4 \end{pmatrix} = 40

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

(3)​

最小木
​

最小総費用は 12 である。

本页目录