広島大学 先進理工系科学研究科 情報科学プログラム 2021年1月実施 専門科目I 問題4

标签：

• Hiroshima-University
• Minimum-Spanning-Tree

Author

samparker, 祭音Myyura

Description

地点 $v \sim z$ 電力網を構築することを考える。 図１に示したグラフ $G$ の各頂点（vertex）は地点 $v ~ z$ のいずれかに対応し、各辺（edge）はその両端に対応する２地点間に電力線が設置可能であることを示し、各辺に添えられた数字はその費用を示す。 以下の設問に答えよ。

(1) グラフ $G$ に関して $0$ または $1$ を要素とする隣接行列（adjacency matrix）$A$ とそれに対応するラプラシアン行列（Laplacian matrix）$L$ を示せ。

(2) グラフ $G$ のスパニング木（spanning tree）は、各地点を一度だけ通り、かつ、閉路（cycle）のないような連結した電力網に対応する。 そのような異なるスパニング木が何通りあるか示せ。 ただし、根拠も示せ。

(3) 前問（2）のうち、最も費用のかからないスパニング木を見つけてその総費用を示せ。

---

Suppose we want to lay out an electric power grid to connect locations $v \sim z$. In Graph $G$ shown in Figure 1, each vertex corresponds to one of the locations $v \sim z$, and each edge represents that an electric power line is possible to construct between the locations at the endpoints of the edge, with which the digit indicates its cost. Answer the following questions:

(1) Show the adjacency matrix $A$ where each element is $0$ or $1$ and the corresponding Laplacian matrix $L$ of Graph $G$.

(2) A spanning tree of Graph $G$ can be defined as a connected electric power grid that visits each location exactly once, not forming a cycle. Show how many different spanning trees are possible for Graph $G$. Also state the reasons for your answer.

(3) Out of the possible spanning trees considered in Question (2) above, find the one with the least total cost and show that total cost.

図 1 Figure 1

题目描述

现要在地点 $v$ 至 $z$ 之间建设电力网。图 1 的图 $G$ 中，每个顶点对应地点 $v,w,x,y,z$ 之一；每条边表示可在其两个端点对应地点之间铺设电力线，边旁数字表示建设费用。

1. 写出图 $G$ 的 $0$-$1$ 邻接矩阵 $A$ 及相应的拉普拉斯矩阵 $L$。
2. 图 $G$ 的生成树对应一个连通且无环、覆盖所有地点的电力网。求不同生成树的总数，并说明依据。
3. 在第 2 问的所有生成树中找出总费用最低的一棵，并给出其总费用。

图的顶点、边及各边费用均见图 1。

考点

• 最小生成树：由图的邻接与拉普拉斯矩阵统计生成树数量，并在带权图中选出总费用最小的生成树。

Kai

(1)

Adjacent matrix

$$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}$$

Degree Matrix $D$

$$D = \begin{pmatrix} 2 & & & & \\ & 4 & & & \\ & & 3 & & \\ & & & 3 & \\ & & & & 4 \end{pmatrix}$$

Laplacian matrix $L$

$$L = D - 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)

Kirchhoff's matrix tree theorem: The number of spanning trees in a graph $G$ is given by $\text{det}(L_G[i])$, for any $i$.

$$\begin{vmatrix} 2 & 0 & 0 & -1 \\ 0 & 3 & -1 & -1 \\ 0 & -1 & 3 & -1 \\ -1 & -1 & -1 & 4 \end{vmatrix} = 40$$

Therefore, there are $40$ different spanning trees in graph $G$.

(3)

A minimum spanning tree of $G$ is $\{zy, yx, xw, wv\}$, whose cost is $8$.