中央大学 理工学研究科 情報工学専攻 2025年2月実施 一般入試（春季）問題II

标签：

• 中央大学
• Kruskal 算法
• Prim 算法

Author

祭音Myyura (co-authored with GPT 6 Astra)

Description

問題 I は必答。問題 II～V のうち、2 問を選んで解答すること。

問題 II

連結無向グラフ $G=(V,E)$ において、最小全域木を求める 2 つのアルゴリズムを以下に記す。

クラスカルのアルゴリズム

1. 辺の重みの昇順にソートする。$T=\varnothing$ と初期化。
2. for $i=1,2,\ldots,m$ do
3. $\quad T\cup\{e_i\}$ が閉路を含まなければ、$T:=T\cup\{e_i\}$。
4. $T$ を出力して終了。

プリムのアルゴリズム

1. 任意の頂点 $s$ を選び、$U=\{s\},\ T'=\varnothing$ と初期化。
2. while $U\ne V$ do
3. $\quad\delta(U)$ の中で重み最小の辺 $e$ を選び、$T':=T'\cup\{e\}$。
4. $\quad U$ に含まれない $e$ の端点を $U$ に追加。
5. $T'$ を出力して終了。

ただし、グラフの辺数を $m$、辺 $e$ の重みを $w(e)$ とするとき、$w(e_1)\leq w(e_2)\leq\cdots\leq w(e_m)$ が成り立つものとする。また、$\delta(U)$ は、端点の一方が集合 $U$ に含まれ、もう一方は $U$ に含まれない辺の集合を表す。以下の問に答えよ。

1. 図 1 のグラフに対して、クラスカルのアルゴリズムを適用する。アルゴリズム終了時の $T$ に含まれる要素を、$T$ に追加された順に答えよ。ただし図 1 のグラフは辺数 13、辺の重みが 1 から 13 の相異なる整数という性質を持つため、辺 $e_k$ は重み $k$ をもつ。

2. 図 1 のグラフに対して、プリムのアルゴリズムを $s=A$ として適用する。アルゴリズム終了時の $T'$ に含まれる要素を $T'$ に追加された順に答えよ。

3. 図 1 のグラフにおいて 2 本の辺の重みを交換すると、最小全域木の辺重み総和が変化する場合がある。最小全域木の辺重み総和がもっとも小さくなる交換のうち、交換に関わる 2 本の辺の重みの和が最小となるものを求めよ。解答は、交換に関わる 2 本の辺（例、$e_1$ と $e_2$）と、辺の重み交換後のグラフにおける最小全域木の辺重み総和の値を記すこと。

4. 図 2 のグラフにおいて $x$ は非負の実数値である。$x$ の値が変化すると、最小全域木の辺重み総和の値や、最小全域木の構造（どの辺が最小全域木に含まれるか）が変化する場合がある。$x$ の値と最小全域木の辺重み総和の値の関係を、横軸に $x$ の値、縦軸に最小全域木の辺重み総和の値をとる座標平面を用いて説明せよ。

题目描述

问题 I 为必答题；从问题 II～V 中选择 2 题作答。

问题 II

对连通无向图 $G=(V,E)$，给出两种求最小生成树的算法。

Kruskal 算法

1. 按边权从小到大排序，初始化 $T=\varnothing$。
2. 对 $i=1,2,\ldots,m$ 执行步骤 3。
3. 若 $T\cup\{e_i\}$ 不含环，则令 $T:=T\cup\{e_i\}$。
4. 输出 $T$ 并结束。

Prim 算法

1. 任取起点 $s$，初始化 $U=\{s\}$、$T'=\varnothing$。
2. 当 $U\ne V$ 时，重复步骤 3、4。
3. 从 $\delta(U)$ 中选择权重最小的边 $e$，令 $T':=T'\cup\{e\}$。
4. 将 $e$ 不在 $U$ 中的端点加入 $U$。
5. 输出 $T'$ 并结束。

其中 $m$ 为边数，$w(e)$ 为边权，且 $w(e_1)\leq\cdots\leq w(e_m)$；$\delta(U)$ 表示恰有一个端点属于 $U$ 的边的集合。图 1、图 2 见上方原图。

1. 对图 1 使用 Kruskal 算法，按加入顺序列出最终集合 $T$ 中的边。图 1 有 13 条边，边权为 1 至 13 的互异整数，因此边 $e_k$ 的权重为 $k$。

2. 对图 1 从 $s=A$ 出发使用 Prim 算法，按加入顺序列出最终集合 $T'$ 中的边。

3. 交换图 1 中两条边的权重可能改变最小生成树的总权重。在使最小生成树总权重达到最小的交换中，求被交换的两条边的原权重之和最小的一种。写出交换的两条边（例如 $e_1,e_2$）及交换后最小生成树的总权重。

4. 图 2 中 $x$ 是非负实数。随着 $x$ 改变，最小生成树的总权重及其边的组成可能改变。在以 $x$ 为横轴、最小生成树总权重为纵轴的坐标平面上，说明两者的关系。

Kai

1. クラスカル法

重み順に辺を調べる。$e_6=BG$ は $B-A-F-G-B$ の閉路を作るため除外し、$e_{10}=DI$ は $D-E-J-I-D$ の閉路を作るため除外する。$e_{11}=CH$ を加えると全頂点が連結し、残る $e_{12},e_{13}$ は加えられない。

$$\boxed{e_1,e_2,e_3,e_4,e_5,e_7,e_8,e_9,e_{11}}$$

の順に追加され、総和は $50$ である。

2. プリム法

$A$ から始めると、順に $F,B,G,H,C,D,E,J,I$ が新たに加わる。従って辺の追加順は

$$\boxed{e_2,e_3,e_4,e_1,e_{11},e_5,e_7,e_9,e_8}.$$

3. 重みの交換

全域木は 10 頂点を結ぶ 9 辺を持つ。交換後も重みの集合は $1,2,\ldots,13$ なので、どの全域木も総和は少なくとも $1+2+\cdots+9=45$ である。

$\boxed{e_2\text{ と }e_{11}}$ の重みを交換すると、$AF$ の重みが 11、$CH$ の重みが 2 になる。辺集合

$$\{e_1,e_3,e_4,e_5,e_6,e_7,e_8,e_9,e_{11}\}$$

は全域木であり、その重みはちょうど $1,2,\ldots,9$。従って交換後の最小全域木の総和は $\boxed{45}$ となり、これが全交換を通じた最小値である。

さらに、45 を達成するには重み 1～9 の全てを使う必要がある。元の $e_1,\ldots,e_9$ は、左の成分 $\{A,B,F,G,H\}$ と右の成分 $\{C,D,E,I,J\}$ に分かれ、左には閉路 $A-B-G-F-A$ がある。1 回の交換で全域木にするには、両成分間の辺 $e_{11},e_{12},e_{13}$ のいずれかを入れ、左の閉路上の辺 $e_2,e_3,e_4,e_6$ のいずれかを外さなければならない。従って交換する元の重みの和は最小でも $2+11=13$ であり、上の交換がこれも達成する。

4. パラメータ $x$ と総和

次の 6 辺を共通部分 $B$ とおく。

$$\begin{gathered} B=\{AF,AB,GH,CD,DE,IJ\},\\ w(B)=2+3+1+5+7+8=26. \end{gathered}$$

クラスカル法によって得られる最小全域木の一例は次のとおり。

$x$ の範囲	$B$ に追加する 3 辺	総和 $W(x)$
$0\leq x\leq3$	$BG,CH,DI$	$26+6x$
$3\leq x\leq4$	$BG,CH,EJ$	$35+3x$
$4\leq x\leq6$	$FG,CH,EJ$	$39+2x$
$6\leq x$	$FG,BC,EJ$	$51$

従って、求めるグラフは以下の折れ線である。

折点は $(0,26),(3,44),(4,47),(6,51)$ で、$x\geq6$ では水平になる。$x=3$ では $DI$ と $EJ$、$x=4$ では $BG$ と $FG$、$x=6$ では $CH$ と $BC$ を交換でき、いずれも総和は変わらない。

Reference

• 中央大学公式問題（2025年度、冊子 p.84／PDF 第85頁；選答方法：冊子 p.82）