2014第30届CMO试题

• 知识点

  >

  二试组合部分

略

用 $30$ 个点表示 $30$ 个人，若两人为熟人，则在他们对应的点之间连一条边，这样得到一个以这 $30$ 个点为顶点集的满足下面条件的简单图 $G$：
（i）图 $G$ 中每一个顶点的度不超过 $5$；
（ii）图 $G$ 的顶点集中的任何五点中均有两点没有连边．
用 $V$ 表示图 $G$ 的顶点集．若 $A \subseteq V$，且集合 $A$ 中任何两点没有连边，则称为图 $G$ 的一个“独立集”，并称元素个数最多的独立集为图 $G$ 的一个“最大独立集”．
（1）首先证明：满足条件的图 $G$ 中最大独立集的元素个数不小于 $6$．
事实上，设 $X$ 为图 $G$ 的一个最大独立集．由 $|X|$ 的最大性，知集合 $V \backslash X$ 中的任一点均有一个邻点在集合 $X$ 中．否则，若 $a \in V \backslash X$ 在集合 $X$ 中没有邻点，则可将 $a$ 加人到集合 $X$ 中形成一个更大的独立集，矛盾．这样在集合 $V\backslash X$ 和 $X$ 之间至少有 $|V\backslash X|=30-| X |$ 条边．
又注意到，集合 $X$ 中每个点的度不超过 $5$，故有 $30-|X| \leqslant 5|X|$ ①．
因此，$|X| \geqslant 5$．
若 $|X|=5$，则由式 ① 取得等号，知上述的 $30-|X|=25$ 条边分布在集合 $X$ 的五个顶点上，即集合 $X$ 中每点的邻点集均为集合 $V\backslash X$ 中五个构成的点集．
因为 $| V\backslash X|=25$，所以，集合 $X$ 中任两点的邻点集不相交．
记 $X=\{a, b, c, d, e\}$．
现考虑 $a$ 的邻点集，记为 $Y_{a}=\left\{y_{1}, y_{2}, y_{3}, y_{4}, y_{5}\right\}$．
由（ii），知集合 $Y_a$ 中有两点不连边，设为 $y_1、y_2$．
由于集合 $X$ 中任意两点的邻点集不相交，故 $y_1、y_2$ 不能为 $b、c、d、e$ 中任一点的邻点．
从而，$\left\{y_{1}, y_{2}, b, c, d, e\right\}$ 为图 $G$ 的独立集且元素个数大于 $5$，矛盾．
这就证明了 $|X|>6$．
（2）其次证明：存在一个满足条件的图 $G$，其最大独立集的元素个数不超过 $6$．将集合 $V$ 分拆为点集 $V_{1}, V_{2}, V_{3}$ 使得 $\left|V_{i}\right|=10(i=1,2,3)$．设 $V_{1}=\left\{A_{1}, A_{2}, \cdots, A_{5}, B_{1}, B_{2}, \cdots, B_{5}\right\}$，将集合 $V_1$ 中的点按下图方式连边，即（i）$A_{i} A_{i+1}(i=1,2, \cdots, 5)$ 连边；
（ii）$B_{i} B_{i+1}(i=1,2, \cdots, 5)$ 连边；
（iii）$A_{i} B_{i}, A_{i} B_{i+1}, A_{i} B_{i-1}(i=1,2, \cdots, 5)$ 连边，其中，$A_{6}=A_{1}, B_{6}=B_{1}, B_{0}=B_{5}$．
点集 $V_2,V_3$ 连边的方式与点集 $V_1$ 的完全一样，且对任意 $1\leqslant i<j \leqslant 3$，点集 $V_i$ 与 $V_j$ 之间不连边．则图 $G$ 的任意顶点的度均等于 $5$，且图 $G$ 中任何五个点中总存在两点不连边．
现任取图 $G$ 的一个最大独立集 $X$．
只需证明：$\left|V_{1} \cap X\right| \leqslant 2$．
事实上，由 $A_{i}, A_{i+1}(i=1,2, \cdots, 5)$ 相邻则 $A_{1}, A_{2}, \cdots, A_{5}$ 中至多有两个属于集合 $X$．
类似地，$B_{1}, B_{2}, \cdots, B_{5}$ 中属于集合 $X$ 的也至多两个．
若 $A_{1}, A_{2}, \cdots, A_{5}$ 中恰有两个属于集合 $X$，不妨设为 $\left\{A_{1}, A_{3}\right\}$．
注意到，$A_1$ 的邻点集与 $A_3$ 的邻点集的并集恰等于 $\left\{B_{1}, B_{2}, \cdots, B_{5}\right\}$．故 $B_{1}, B_{2}, \cdots, B_{5}$ 均不属于集合 $X$．
类似地，若 $B_{1}, B_{2}, \cdots, B_{5}$ 中恰有两个属于集合 $X$，则 $A_{1}, A_{2}, \cdots, A_{5}$ 均不属于集合 $X$，这就证明了 $\left|V_{1} \cap X\right| \leqslant 2$．
类似地，$\left|V_{2} \cap X\right| \leqslant 2,\left|V_{3} \cap X\right| \leqslant 2$．
故 $|X|=|V \cap X|=\left|V_{1} \cap X\right|+\left|V_{2} \cap X\right|+\left|V_{3} \cap X\right| \leqslant 6$．
因此，图 $G$ 符合要求．
综合（1）、（2），知所求的 $k$ 值为 $6$．