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

标签：

• 中央大学
• 图着色与色多项式
• 团
• 贪心算法

Author

祭音Myyura (Based on 中央大学の公式解答例 refined with GPT 6 Astra)

Description

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

問題 IV.

グラフ $G=(V,E)$ の頂点に色を塗ることを考える。$k$ 個の色を用いて、どの辺の両端点も互いに異なる色で塗り分けるとき、$G$ は $k$ 彩色可能であるという。$G$ の頂点の彩色に必要な $k$ の最小値を彩色数とよび、$\chi(G)$ で表す。

図 1 は 3 彩色の例である。頂点 a から頂点 d の○の中にある数字が色を表す。隣接する頂点には異なる番号（色）が割り当てられていることが確認できる。この例では、隣接していない頂点 b と d には同じ番号（同じ色）が割り当てられている。

1. 図 2 のグラフの頂点をできるだけ少ない色で彩色せよ。解答欄には図 2 のグラフを描き、グラフの頂点を表す○の中に、色に対応する番号を書いて解答すること。

2. 頂点 $v$ に接続する辺の数をその頂点の次数とよび、$d_v$ で表す。以下は頂点彩色のアルゴリズムである。

   彩色アルゴリズム

   ステップ 1．頂点を次数の大きい順に並べ、$v_1,v_2,\ldots,v_n$ とおく（つまり $d_{v_1}\geq d_{v_2}\geq\cdots\geq d_{v_n}$ が成り立つ）。次数が同じ頂点はどちらを先にしてもよい。

   ステップ 2．$v_1,v_2,\ldots,v_n$ の順に頂点を選び、各 $v_i$ に割り当て可能なもっとも小さい番号の色（$v_i$ に隣接する $v_1$ から $v_{i-1}$ の頂点に使用されていない番号で最小のもの）を割り当てる。

   彩色アルゴリズムを図 2 のグラフに適用して得られる頂点の彩色を答えよ。解答欄には図 2 のグラフを描き、グラフの頂点を表す○の中に、色に対応する番号を書いて解答すること。ステップ 1 で定めた頂点の順序も答えよ。

3. 彩色アルゴリズムは最小の色数で彩色するとは限らない。このアルゴリズムが $\chi(G)$ 個の色で彩色しないグラフ $G$ の例（グラフとステップ 1 の頂点の順序）を述べ、アルゴリズムが $\chi(G)$ 個の色で彩色しない理由を説明せよ。

4. 彩色アルゴリズムは彩色数 $\chi(G)$ の上界を与えている。この上界を理由とともに答えよ。数式で記述してもよいし、文章で説明してもよい。

5. 彩色数 $\chi(G)$ の下界として適切なものを答えよ。例などを使って分かりやすく説明すること。

题目描述

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

问题 IV

考虑给图 $G=(V,E)$ 的顶点着色。如果能用 $k$ 种颜色使每条边的两个端点颜色不同，则称 $G$ 可以进行 $k$ 着色。所需颜色数 $k$ 的最小值称为色数，记为 $\chi(G)$。

图 1 为 3 着色的例子，顶点 a 至 d 的圆圈内数字表示颜色。相邻顶点分配不同的编号（颜色）；不相邻的 b 和 d 使用相同的编号（颜色）。原图见上方图 1、图 2。

1. 用尽可能少的颜色为图 2 着色。在答题区域画出图 2，并在表示各顶点的圆圈内写出对应颜色的编号。

2. 与顶点 $v$ 相连的边数称为其度数，记为 $d_v$。考虑以下顶点着色算法。

   步骤 1：按度数从大到小排列顶点，记为 $v_1,v_2,\ldots,v_n$，即 $d_{v_1}\geq d_{v_2}\geq\cdots\geq d_{v_n}$。度数相同的顶点可任意排序。

   步骤 2：依次处理 $v_1,v_2,\ldots,v_n$。对每个 $v_i$，选择当前可以使用的最小颜色编号，即在已处理且与 $v_i$ 相邻的顶点中尚未使用的最小编号。

   将该算法应用于图 2，写出着色结果。在答题区域画出图 2，并在各顶点圆圈内填写颜色编号；还须写出步骤 1 采用的顶点顺序。

3. 该算法不一定使用最少颜色。给出一个未能用 $\chi(G)$ 种颜色着色的例子，包含图 $G$ 和步骤 1 的顶点顺序，并说明为何没有得到最少颜色数。

4. 该算法给出了色数 $\chi(G)$ 的一个上界。写出上界并说明理由，可用公式或文字表述。

5. 给出色数 $\chi(G)$ 的一个适当下界，并结合例子等作清楚解释。

Kai

1. 最少色数による彩色

頂点 $\{a,b,c,f\}$ は互いに全て隣接しており、完全グラフ $K_4$ をなす。従って少なくとも 4 色が必要である。一方、次の彩色は全ての辺の両端を異なる色にする。

$$(a,b,c,d,e,f)=(3,4,2,3,2,1).$$

よって $\boxed{\chi(G)=4}$ である。

2. アルゴリズムの適用

各頂点の次数は

$$d_f=5,\quad d_c=4,\quad d_a=d_b=d_d=3,\quad d_e=2.$$

従って、ステップ 1 で $\boxed{f,c,a,b,d,e}$ の順を選べる。ステップ 2 は次のように進む。

頂点	先に彩色した隣接頂点の色	割り当てる色
$f$	なし	$1$
$c$	$1$	$2$
$a$	$1,2$	$3$
$b$	$1,2,3$	$4$
$d$	$1,2$	$3$
$e$	$1,3$	$2$

結果は 1 の解答図と同じで、$(a,b,c,d,e,f)=(3,4,2,3,2,1)$ となる。

3. 最少色数にならない例

頂点集合を $U=\{u_1,u_2,u_3\}$、$W=\{w_1,w_2,w_3\}$ とし、$u_iw_j$ を $i\ne j$ のときに限って辺とする。このグラフは長さ 6 の閉路であり、全頂点の次数は 2 である。二部グラフなので $U$ を色 1、$W$ を色 2 とすれば彩色でき、辺を持つから $\chi(G)=2$ である。

全頂点の次数が等しいため、ステップ 1 では $u_1,w_1,u_2,w_2,u_3,w_3$ という順が許される。この順で貪欲に彩色すると、

$$(u_1,w_1,u_2,w_2,u_3,w_3)=(1,1,2,2,3,3).$$

$u_2$ は色 1 の $w_1$ に隣接するため色 2 となり、$w_2$ も色 1 の $u_1$ に隣接するため色 2 となる。$u_3$ は色 1 の $w_1$ と色 2 の $w_2$ に隣接し、$w_3$ は色 1 の $u_1$ と色 2 の $u_2$ に隣接するので、いずれも色 3 が必要となる。従ってこの順序では最適な 2 色を超えて 3 色を使用する。

4. 上界

最大次数を $\Delta(G)=\max_{v\in V}d_v$ とする。頂点 $v_i$ の処理時に禁止される色は、既に彩色した隣接頂点の色だけであり、その種類数は高々 $d_{v_i}\leq\Delta(G)$ である。従って、色 $1,2,\ldots,\Delta(G)+1$ のうち少なくとも一つは使用できる。

このアルゴリズムで高々 $\Delta(G)+1$ 色の正しい彩色が得られるので、

$$\boxed{\chi(G)\leq\Delta(G)+1}.$$

5. 下界

最大クリークの頂点数を $\omega(G)$ とすると、

$$\boxed{\omega(G)\leq\chi(G)}.$$

クリーク内の任意の 2 頂点は隣接するため、その頂点数と同じ数の異なる色が必要だからである。例えば図 2 には $\{a,b,c,f\}$ という 4 頂点クリークがあり、$\chi(G)\geq4$ と分かる。1 の 4 彩色と合わせれば最適性が確定する。

Reference

• 中央大学公式問題（2026年度、冊子 p.18／PDF 第19頁；選答方法：冊子 p.14）
• 中央大学公式解答例・出題の意図（2026年度、冊子 p.22／PDF 第23頁）