速通离散数学（2）

一节课也没上过的摆子开始水学分了（bushi）

挑个别我不太熟悉的东西写一下，大部分都是学 oi 时候就会了的。

2.1.3 顶点与边的连通度

对于连通图 \(G\)，定义点连通度为最少需要删去多少点才能使其不连通，边连通度为最少需要删去多少边才能使其不连通。分别记作 \(\kappa(G),\lambda(G)\)。那么 \(\kappa(G)\le\lambda(G)\le\delta(G)\)，其中 \(\delta(G)\) 为图中点度数的最小值。根据这个性质可以推出 \(\kappa(G)\le\lceil\dfrac{2m}{n}\rceil\)，因为 \(\delta(G)\le\lceil\dfrac{2m}{n}\rceil\)。

2.4 哈密顿回路

任意图哈密顿回路的判定是 NP 的，但是存在一些判定哈密顿回路的充分条件。

定理：如果连通图中任意两点度数之和 \(\ge n-1\) 则图中存在哈密顿路径。

证明：假设 \(p_1\to p_2\to \cdots\to p_m\) 为图中最长的不经过重复点的路径，如果 \(m=n\) 则命题成立，否则因为 \(p_1,p_m\) 无法继续延申，所有与 \(p_1,p_m\) 相连的点都属于 \(p_2,p_3\cdots,p_{m-1}\)。我们先证明存在一个经过这 \(m\) 个点的简单环：如果 \(p_1,p_m\) 之间有边则显然可以首尾相连成环，否则必然存在 \(i\) 使得 \(p_i\) 与 \(p_1\) 相连，\(p_{i-1}\) 与 \(p_m\) 相连，这样 \(p_1\to\cdots\to p_{i-1}\to p_{m}\to\cdots\to p_i\) 可以首尾相接成环，否则 \(deg_{p_1}+deg_{p_m}\le m-1<n-1\)。这样因为这 \(m\) 个点首尾相接成环，并且图连通，必然存在不在这个环里的点与环里某个点相连，从那个点处断环成链并接上新的点可以得到更长的路径，因此 \(m=n\)。

推论：如果连通图中任意两点度数之和 \(\ge n\) 则图中存在哈密顿环。

证明：用上面的方法证明最后得到的 \(n\) 个点的路径也可以成环即可。

定义一张图的闭合图为每次选择两个没有边相连的点 \(i,j\) 满足 \(deg_i+deg_j\ge n\)，加入 \((i,j)\) 这条边，如此操作下去直到不能操作为止以后得到的图。一张图的闭合图显然是唯一的，因为如果两个闭合图 \(G_1,G_2\) 不相等，那么找出得到 \(G_1\) 的过程中第一个不在 \(G_2\) 中的边 \((i,j)\)，那么这个时候已经有 \(deg_i+deg_j\ge n\) 了，最后 \(G_2\) 里肯定也有，因此 \(G_2\) 不是闭合图。

定理：简单图 \(G\) 存在哈密顿回路当且仅当其闭合图存在哈密顿回路。

证明：只要证明每次加边 \((i,j)\) 不会改变哈密顿回路存在性即可。显然不会从有变成无，如果是从无变成有，那么必然是因为所有的哈密顿路径都以 \(i,j\) 作为端点，因为 \(d_i+d_j\ge n\)，那根据前面的证明它必然可以变成环，矛盾。

3.4 回路矩阵与割集矩阵

对于一张连通图 \(G\)，其包含边 \(e_1=(a_1,b_1),e_2=(a_2,b_2),\cdots,e_n=(a_n,b_n)\)，定义其完全回路矩阵 \(C_e\) 为一个规模为 \(\text{简单环个数}\times m\) 的矩阵，并且需要给每个简单环指定一个方向，第 \(i\) 行第 \(j\) 列为 \(0\) 当且仅当 \(e_j\) 不在环中，为 \(1\) 当且仅当环上 \(e_j\) 的方向是 \(a_j\to b_j\)，为 \(-1\) 当且仅当环上 \(e_j\) 的方向是 \(b_j\to a_j\)，显然这个矩阵的规模是指数级别的。

随便指定一棵生成树 \(T\)，定义基本回路矩阵 \(C_f\) 为所有包含恰好一个非树边的环组成的矩阵。显然这个矩阵大小的 \((m-n+1)\times m\) 级别的，并且各行线性无关。完全回路矩阵的每一行都可以表示为基本回路矩阵的线性组合。

设 \(B\) 为图的关联矩阵（\(n\times m\) 的矩阵，第 \(i\) 行第 \(j\) 列为 \(0\) 当且仅当 \(a_j\ne i,b_j\ne i\)，为 \(1\) 当且仅当 \(a_j=i\)，为 \(-1\) 当且仅当 \(b_j=i\)），那么 \(BC_e^T=0\)。

对于一张连通图 \(G\)，定义其的一个割集为一个边集使得将这个边集中的边去掉以后连通分量数量加 \(1\)，且去掉这个割集的真子集以后连通分量数量不变。定义其完全割集矩阵 \(S_e\) 为一个规模为 \(\text{割集个数}\times m\) 的矩阵，同理需要给每个割集指定一个方向，第 \(i\) 行第 \(j\) 列为 \(0\) 当且仅当 \(e_j\) 不在割集中，为 \(1\) 当且仅当割集方向是 \(a_j\to b_j\)，为 \(-1\) 当且仅当割集方向是 \(b_j\to a_j\)。

随便指定一棵生成树 \(T\)，定义基本回路矩阵 \(S_f\) 为所有包含恰好一个树边的割集组成的矩阵。显然这个矩阵大小的 \((n-1)\times m\) 级别的，并且各行线性无关。完全割集矩阵的每一行都可以表示为基本割集矩阵的线性组合。

对于同一连通图的割集矩阵和回路矩阵而言，有 \(S_eC_e^T=0\)。

4.1, 4.2 平面图

对于一张点数为 \(n\)，\(m\) 条边，\(d\) 个域，\(k\) 个连通分量的平面图而言，有 \(m-n+d=k+1\)。

对于平面图连通图而言，如果其不存在割边，并且每个域的边界数至少是 \(t\)，那么 \(m\le\dfrac{t(n-2)}{t-2}\)。

证明：因为图中不存在割边，故 \(2m\ge td\)，\(2m\ge t(m-n+2)\)，\(tn-2t\ge (t-2)m\)，\(m\le\dfrac{t(n-2)}{t-2}\)。

定义一张简单平面图是极大的，当且仅当加入任何一条新的边以后图都不是平面图。

极大平面图有性质：每个域的边界数都是 \(3\)。

证明：如果一个域由 \((p_1,p_2),(p_2,p_3),\cdots,(p_{m-1},p_m),(p_m,p_1)\) 围成，且 \(m\ge 4\)，如果 \((p_1,p_3)\) 之间没有边，那么在这个区域里面加入 \((p_1,p_3)\) 之后图还是平面图，不符合极大平面图的定义，故 \((p_1,p_3)\) 之间有边，并且因为这是平面图的一个域，故这条边在平面图中这个 \(m\) 边形的外侧。同理 \((p_2,p_4)\) 之间也有边并且也在外侧，这样这两条边必然会相交，不符合平面图的定义。

而很明显，极大平面图是连通图（否则在不同连通块中随便挑一个点相连还是平面图），并且不存在割边（否则在割边对应的两个边双里随便挑一个点相连还是平面图）。这样每条边都是两个域的边界，即 \(3d=2m\)，\(d=m-n+2\)，故在极大平面图中，必然有 \(m=3n-6\)，\(d=2n-4\)。

因为任意一张平面图通过不断加边得到平面图的过程中边数和域数都单调不降，因此任意一张平面图都有 \(m\le 3n-6,d\le 2n-4\)。

任意平面图中必然存在度数 \(\le 5\) 的点，因为如果每个点度都 \(\ge 6\)，那么必然有 \(m\ge 3n\)。

4.3 非平面图

\(K_5\) 和 \(K_{3,3}\) 是非平面图，定义 \(K\) 型子图为在这两种图的边上加入一些 \(2\) 度点得到的图，那么一张图是非平面图当且仅当其存在一个子图是 \(K\) 型子图，换句话说，不断缩 \(2\) 度点后存在的图中包含 \(K_5\) 和 \(K_{3,3}\)。

4.4 对偶图

对于一张平面图而言，定义其对偶图为，将图中每个域看成点以后，对于每条边而言，将这条边两侧的域连边以后得到的新图。一张图有对偶图当且仅当其是平面图，并且对偶图唯一，一张图的对偶图也是平面图，并且连通平面图的对偶图的对偶图就是其自身。

对于平面图而言，一定可以将其每个区域染成 \(5\) 种颜色之一使得相邻区域不同色（平面图五色定理）

证明：做对偶图 \(G^*\)，等价于给 \(G^*\) 的每个顶点染成五种颜色之一使得有边相连的点不同色。因为对偶图一定是平面图，我们考虑对一般平面图证明这个性质。对点数进行归纳，因为平面图中必然存在度 \(\le 5\) 的点，因此考虑提取这个点出来，设为 \(x\)，去掉这个点以后，根据归纳假设，剩余部分可以染成 \(5\) 种颜色之一使得任意相邻点不同色，而如果 \(x\) 度数 \(\le 4\)，或者与其相连的点中的点没有用完五种颜色，那么必然存在没用完的颜色，将 \(x\) 染成这个颜色即可。否则设 \(x\) 相连的点按照逆时针顺序分别是 \(v_1,v_2,v_3,v_4,v_5\)，染的颜色分别是 \(c_1,c_2,c_3,c_4,c_5\)，考虑由 \(c_1,c_3\) 颜色的点构成的导出子图，如果 \(v_1,v_3\) 不在一个连通分量里，那么交换 \(v_3\) 所在的连通分量里所有染 \(c_1,c_3\) 颜色的点的颜色，然后将 \(x\) 染成 \(c_3\) 即可。否则，因为 \(G^*\) 是平面图，\(c_1,c_3\) 这条链上的点肯定把 \(v_2,v_4\) 所在的连通分量隔开来了，这样交换 \(v_2\) 所在的连通分量里所有染 \(c_2,c_4\) 颜色的点的颜色，然后将 \(x\) 染成 \(c_4\) 即可。根据归纳法可知任意平面图都可以 \(5\)-染色。

4.5 色数与色数多项式

对于图 \(G\)，定义其色数为最少需要的颜色数 \(k\) 使得能够将每个点染成 \(k\) 种颜色之一并且有边相连的点不同色，记作 \(\gamma(G)\)。同理定义边色数 \(\beta(G)\)。因为边色数可以通过简单的边转点转化为色数，所以我们一般讨论色数。

平面图的对偶图的色数 \(\le 2\) 当且仅当原图存在欧拉回路。

证明：对偶图的每个环都是偶环当且仅当原图中每个点的度数都是偶数。

对于任意图 \(G\)，\(\gamma(G)\le d_0+1\)，其中 \(d_0=\max d(v_i)\)。

证明：对图的大小进行归纳，设 \(G\) 中度最大的点为 \(x\)，那么删去 \(x\) 以后图中最大点的度数必然不超过 \(d(x)\)，因此可以进行 \(d(x)+1\) 染色，再随便给 \(x\) 挑一个邻居没用过的颜色即可。

事实上有更强的结论：

对于任意图 \(G\)，\(\gamma(G)\le 1+\max\delta(G')\)，其中 \(G'\) 是 \(G\) 的导出子图，\(\delta(G')\) 为导出子图 \(G'\) 中所有点的最小度。

证明：\(G\) 为空时显然正确。否则找出极小的色数等于原图色数的导出子图 \(H\)，因为 \(\forall v\in H\)，都有 \(\gamma(H-v)=k-1\)，故 \(H\) 中所有点都与恰好 \(k-1\) 个 \(H\) 中的点相连，即 \(\delta(H)=k-1\)，故 \(\gamma(G)=1+\delta(H)\le 1+\max\delta(G')\)。

设 \(f(G,t)\) 为将 \(G\) 中每个点染成 \(t\) 种颜色之一使得有边相连的点不同色的方案数，\(i,j\) 为 \(G\) 中不相邻的两个点，那么 \(f(G,t)=f(\bar{G}_{i,j},\circ{G}_{i,j})\)，其中 \(\bar{G}_{i,j}\) 为在 \(G\) 中加入 \((i,j)\) 以后得到的新图，\(\circ{G}_{i,j}\) 为将 \(i,j\) 合并成一个点以后得到的新图（分 \(i,j\) 同色异色考虑即可）。这种计算方法适合计算近似完全图的图的色数。