图论与组合：作业 / 1.1

设其邻接矩阵 $A\subset\{0,1\}^{(n+m)\times (n+m)}$

$a_{i,j}=1$ 当且仅当满足下列两个条件之一:

• $i\leqslant n$ 且 $j>n$.
• $i>n$ 且 $j\leqslant n$.

其余情况 $a_{i,j}=0$.

独立数: 4.

首先存在一种方案 $\{12,13,14,15\}$ 是一个大小为 4 的独立集.

其次, 假设存在大小为 5 的独立集, 类似任两个不相邻的顶点恰有唯一一个公共邻居可以推出当两组不相邻顶点不完全一致时, 其对应的公共邻居也不一样.

所以对于这个大小为 5 的独立集, 任选两个顶点就会对应一个邻居, 且这些邻居都是不同的, 所以一共会有 $\binom{5}{2}$ 个邻居, 这样总共就有 5+10=15 个点超出总共 10 个点, 矛盾.

所以最大的独立数是 4.

团数: 2.

首先存在一种方案 $\{12, 34\}$ 是一个大小为 2 的团.

其次由于围长是 5, 故不存在 3-cycle, 所以不存在大小为 3 的团, 进而不存在更大的团.

所以最大的团数是 2.

染色数 3:

首先存在一种方案 $\{12,13,14,15\},\{23,24,25\},\{34,35,45\}$ 可以划分为三个独立集, 故染色数不超过 3.

其次, 由于存在长的为 5 的奇环, 所以不可能是二部图, 即染色数不可能是 2.

所以染色数是 3.

\

• 顶点数目: $\binom{n}{k}$, 边的数目: $\frac 1 2 \binom{n}{k}\binom{n-k}{k}$.

顶点数目显然, 边的数目利用对称性, 计算每个顶点的度数再除以 2.

• 团数: $\left\lfloor\dfrac{n}{k}\right\rfloor$.

首先存在构造 $\{12\cdots k, k+1\ k+2 \cdots 2k,\ldots\}$ 是一个大小为 $\left\lfloor\dfrac{n}{k}\right\rfloor$ 的团.

其次假设存在更大的团, 不妨设大小为 $\left\lfloor\dfrac n k \right\rfloor+1$, 由于任意两个顶点交集为空, 所以一共需要元素数量为 $k\left(\left\lfloor\dfrac n k \right\rfloor+1\right)>n$ 故不存在.

• 独立数:

存在构造, 我们将所有包含 $1$ 的顶点取出, 共有 $\binom{n-1}{k-1}$ 个顶点, 这些顶点构成一个独立集, 所以独立数大于等于 $\binom{n-1}{k-1}$.

• 染色数:

存在构造, 记 $c(v)$ 表示顶点 $v$ 的颜色, $\min v$ 表示 $v$ 中最小的数, 那么当 $\min v\leqslant n-2k+1$ 时我们取$c(v)=\min v$, 其余情况我们取 $c(v)=n-2k+2$.

验证合法性,

首先对于颜色 $c\in[1,n-2k+1]$, 其中的顶点一定包含数 $c$, 从而两两之间无边, 每个颜色都形成一个独立集.

而对于颜色 $c=n-2k+2$, 其中的顶点由 $2k-1$ 个数中选取 $k$ 个数构成, 根据抽屉原理, 任意两个顶点至少存在 $\left\lfloor \frac {k+k}{2k-1}\right\rfloor=1$ 个相同的数, 所以任意两个点之间没有边, 形成独立集.

综上该构造是符合染色要求的, 所以染色数不超过 $n-2k+2$.