[TOC] ## 课程简介 **离散数学** 研究对象：离散个体以及结构关系 **图论与代数结构** 的书还讨论了 平面图与图的着色、图的匹配问题、网络流、抽象代数的内容 ## 图的基本概念 主要复习： - 图的基本概念 - 有向图的度=入度+出度 - 支撑子图/生成子图 v.s. 导出子图； - 图的代数表示：What's 关联矩阵（$n\times m$ 的矩阵）、边列表和正向表； - 证明方法：反证法，数学归纳法，直接证明构造法。 - 含有 $n$ 个结点的简单图一共有 $2^{n(n-1)/2}$ 个。 - 道路与回路 - 道路可以表示为 $v,e,v,e,\cdots,v$，回路在道路的基础上，要求首尾节点相同。 - 如果 $P$ or $C$ 中没有重复出现的边, 称之为 **简单道路** 或简单回路, 若其中结点也不重复, 又称之为 **初级道路** 或初级回路。 - 区别欧拉回路（每条边经过一遍）和哈密顿回路（每个点经过一遍） - 完全图哈密顿回路的个数 $\displaystyle \frac{1}{2}(n-1)!$. - Peterson 图：存在哈密顿道路而无哈密顿回路； - 哈密顿道路判定的结论： - $\forall i,j , d(v_i)+d(v_j) \ge n-1$ 证明：先证明联通，然后再取极大路径，先构造回路，然后再扩展成更长的道路，直到长度 $l=n$. - $n$ 个人中，两个人合起来都认识其余 $n-2$ 个人。证明：若 $v_i,v_j$ 互相认识，则 $d(v_i)+d(v_j) \ge n$；否则一定认识同一个人，出现重复，$d(v_i)+d(v_j) \ge n-1$. - 也可以这么证明：取极长回路，一定会包含所有节点，如果不包含 $v_i$，首尾节点其中一个一定和 $v_i$ 相连。 - 哈密顿回路判定的结论： - $\forall i,j, d(v_i)+d(v_j) \ge n$ 证明：运用上面的结论得到哈密顿道路，然后再扩展成为回路。 - $m\ge C_{n-1}^2 +2$ 运用上面的结论证明。 - 不存在哈密顿回路的判定： - $G-V$ 的导出子图联通支数大于 $|V|$. - 可以被画作二分图，而有奇数个节点。可以被画作二分图，但是两个点集的大小不相同。 - 不存在哈密顿道路的判定： - $G-V$ 的导出子图联通支数大于 $|V|+1$. - 闭合图：若简单图有不相邻节点 $v_i$ 与 $v_j$ 满足 $d(v_i)+d(v_j) \ge n$，则 $G$ 存在 H 回路当且仅当 $G+(v_i,v_j)$ 存在 H 回路。若加边前不存在，则必然存在 H 道路，但是因为不能构造初级回路所以 $d(v_1)+d(v_l )\le n-1 记忆：生成子图对节点集有要求，导出子图对边有要求。 **图的运算** 交 $G_1 \cap G_2=(V_1 \cap V_2,E_1 \cap E_2)$、并 $G_1 \cup G_2=(V_1\cup V_2,E_1 \cup E_2)$、差（$G_1-G_2=(V_1,E_1-E_2)$，如果出现孤立点，删掉）、补（$\overline{G_1}=K_n-G_1$）. 对称差（$G_1 \oplus G_2 = (G_1-G_2) \cup (G_2-G_1)$） **图的运算** - 删点 $G-v$（还要删去连边） **图的同构** 定义：给定图 $G_1=(V_1,E_1)$ 以及图 $G_2=(V_2,E_2)$，如果在 $V_1$ 和 $V_2$ 之间存在双射使得 $$ (u,v) \in E_1 \iff (f(u),f(v)) \in E_2 $$ 则 $G_1$ 和 $G_2$ 同构，记为 $G_1 \cong G_2$。 必要条件： - $|V(G_1)|=|V(G_2)| \quad |E(G_1)| = |E(G_2)|$. - $G_1$ 和 $G_2$ 节点度的非增序列相同。 - $G_1$ 和 $G_2$ 的导出子图相同。 Peterson 图。 image-20240115003453344 ### Ramsey 定理 对于红色 $K_s$ 或者蓝色 $K_t$，一定能够找一个最小的 $n$，使得若对完全图 $K_n$ 中的所有线段染红色或蓝色，一定会出现红色 $K_s$ 或者蓝色 $K_t$. - $R(2,n)=n$. - $R(3,3)=6$（鸽笼原理） - $R(m,n)=R(n,m)$. - $R(s,t) \le R(s-1,t)+R(s,t-1) \quad (s,t \in \Z^* ,s,t>2)$. 证明：考虑 $R(s-1,t)+R(s,t-1)$ 个人…… ### 代数表示 **邻接矩阵 (adjacency matrix)** $$ a_{ij} = \left\{\begin{matrix}1, &(v_i,v_j) \in E,\\ 0 , & otherwise\end{matrix}\right. $$ 无向图的邻接矩阵是对称矩阵；无向简单图邻接矩阵的第 $i$ 行之和为结点 $v_i$ 的度。 **权矩阵** $$ a_{ij} = \left\{\begin{matrix}w_{ij}, &(v_i,v_j) \in E,\\ 0 , & otherwise\end{matrix}\right. $$ **关联矩阵 (incidence matrix)** 有向图 $G=(V,E)$ 的关联矩阵是一个 $n \times m$ 矩阵 $B$，其元素为： $$ b_{ij} = \left\{\begin{matrix}1, & e_j=(v_i,v_k) \in E,\\-1,& e_j=(v_k,v_i) \in E,\\ 0 , & otherwise\end{matrix}\right. $$ - 每列只有两个 $1,-1$. $1$ 代表出，$-1$ 代表入； - 第 $i$ 行 1 的个数为 $d^+(v_i)$，-1 的个数为 $d^-(v_i)$。 - 可以表示重边，不能表示自环。 ------ 图的矩阵表示： - 矩阵表示法唯一、直观。 - 不能表示重边或者自环。 - 需要较大的存储空间。 **边列表** 对于每条边 $e_k=(v_i,v_j)$，有： $$ A[k]=i,B[k]=j,Z[k]=w_k $$ **正向表** 有向图用 $n+1$ 维向量 $A$ 和 $m$ 维向量 $B$ 来表示。 - $A(i)$ 表示存储 $v_i$ 的第一个直接后继在 $B$ 中的地址，$A(n+1)=m+1$. - $B$ 存储 $m$ 个直接后继节点的编号。 ![image-20230920104330579](https://notes.sjtu.edu.cn/uploads/upload_f05f768225c7a2cdd7a9783c447a9ea1.png) - $d^+(v_i)=A(i+1)-A(i)$. - $\displaystyle A(i)=\sum_{j=1}^{i-1} d^+(v_j)+1$. - 从 $B(A(i))$ 到 $B(A(i+1)-1)$ 的任意一个值，都是 $v_i$ 的直接后继。 但是插入删除操作复杂度高。 **邻接表** ![image-20230920110117565](https://notes.sjtu.edu.cn/uploads/upload_f503794eba4e92a8fff3a3c269e12489.png) ## 道路与回路 ### 道路与回路 **有向道路** 有向图 $G$ 中边序列 $P=(e_{i_1},e_{i_2},\cdots,e_{i_q})$，其中 $e_{i_j}=(v_k,v_i)$ 满足 $v_k$ 是 $e_{i_{j-1}}$ 的终点，$v_i$ 是 $e_{i_{j+1}}$ 的起始点。 **有向回路** $e_{i_q}$ 的终点也是 $e_{i_1}$ 的始点。 **道路/链** 无向图 $G=(V, E)$ 中, 若点边交替序列 $P=\left(v_{i 1}, e_{i 1}, v_{i 2}, e_{i 2}, \cdots, e_{i q-1}, v_{i q}\right)$ 满足 $v_{i k}, v_{i k+1}$ 是 $e_{i k}$ 的两个端点, 则称 $P$ 是 $G$ 中的一条链, 或道路。如果 $v_{i q}=v_{i 1}$, 则称 $P$ 是 $G$ 中的一个圈, 或回路。 > 一个点可以成为道路，但是不能成为回路。 如果 $P$ 中没有重复出现的边, 称之为 **简单道路** 或简单回路, 若其中结点也不重复, 又称之为 **初级道路** 或初级回路。 **回路/圈** **极长路径/初级道路** $P$ 是一条初级道路（点不重复），始点和终点都不与 $P$ 外的顶点相邻。 **扩大初级道路法** 求极长路径。 **弦** 设 $C$ 为简单图 $G$ 中含节点数大于 3 的一个初级回路，如果结点 $v_i$ 和 $v_j$ 在 $C$ 中不相邻，而边 $(v_i,v_j) \in E(G)$，则 $(v_i,v_j)$ 是 $C$ 的一条弦。 ![image-20230920112106731](https://notes.sjtu.edu.cn/uploads/upload_147a4f999b94006f575876fd372a945f.png) **联通性** - 若无向图 $G$ 的任意两个节点之间都存在道路，则 $G$ 是联通的。 - 对于有向图 $G$，若去掉方向，是联通的，则称为(弱)联通。 - 若 $G$ 的联通子图 $H$ 不是 $G$ 其它任何联通子图的真子图，则称 $H$ 是 $G$ 的 **极大联通子图**，或称为 **联通支**。 - 设 $v$ 是 $G$ 的一个结点，若 $G-v$ 的联通支数比 $G$ 多，则称 $v$ 是 $G$ 的一个割点。 - 若 $G$ 是简单图，试证明 $\displaystyle m>\frac{1}{2}(n-1)(n-2)$ 时，$G$ 是连通图。若分为两个部分…… **二分图** - 若 $V(G)$ 能够划分为 $V_1,V_2$，使得 $G$ 中每条边的两个结点分别属于 $V_1,V_2$，则称 $G$ 是二分图。 - 充分必要条件：不存在奇环。 - 证明 **必要性**，若不存在环，就是一棵树。 - 如果存在环，则环上的点属于的点集应该是互相间隔的，因此不存在奇环。 - 证明 **充分性**，黑白染色。设 $v_0$ 是 $G$ 中任意一点，定义 $V_1=\{v \mid v \in G,d(v,v_0) 为偶数\}$，$V_2=V-V_1$. - 若 $V_1$ 中存在相邻节点 $v_1,v_2$，则存在奇环 $v_0 \to v_1 \to v_2 \to v_0$，长度为奇数；$V_2$ 亦然。 **道路与回路的判定** - Warshall 算法，$u,v$ 之间长为 $k$ 的道路数目为 $A_{u,v}^k$，其中 $A$ 为 $G$ 的邻接矩阵。所有道路总数：$\displaystyle \left(\sum_{i=1}^{n-1} A^i\right)_{u,v}$. 也可以计算 $\displaystyle (I+A)^n$. ![image-20230922142228927](https://notes.sjtu.edu.cn/uploads/upload_88450209929276e5d4cf0babf0688adb.png) - 搜索法、邻接矩阵法。 ### 欧拉回路 欧拉：每条路都走一遍。 **欧拉回路**：连通图 $G$ 中一条经过所有边的简单回路。七桥问题就是判断是否存在欧拉回路。 **欧拉道路**：连通图 $G$ 中一条经过所有边的简单道路。 **欧拉图**：具有欧拉回路的图。 **欧拉半图**：具有欧拉道路但是无欧拉回路的图。 -------- 定理：无向 **连通图** $G$ 中存在欧拉回路的充要条件为 $G$ 中各节点的度都是偶数。 - **必要性** 每个点的进入次数和出去次数相等。 - **充分性** 当 $m=1$ 时，是自环，是欧拉图。当 $m \le k$ 时结论成立，证明 $m=k+1$ 时结论也成立。一定存在回路 $C$（蓝色），去掉回路 $C$ 的部分，剩下的联通支满足每个节点都是偶数的条件，而且边数 $\le k$，然后可以构造欧拉回路…… ![image-20230922144058839](https://notes.sjtu.edu.cn/uploads/upload_656eddfbfe33291472ebd46c34964e96.png) --------- 定理: 无向连通图 $G$ 中存在欧拉道路(欧拉半图)的充要条件是 $G$ 中只有两个度为奇数的结点。 证明: 连接这两顶点，则有回路；再删去这条边。 ------ 定理：有向连通图 $G$ 中存在欧拉回路的充要条件为 $G$ 中节点的入度和出度相等。 定理：有向连通图 $G$ 是 **欧拉半图** 的充要条件为至多有两个顶点，其中一个出度比入度大一，一个入度比出度大一。 -------- 定理：设连通图 $G=(V,E)$ 中有 $2k$ 个度数为奇数的节点，那么 $E(G)$ 可以划分为 $k$ 条简单道路。$k$ 笔画。 证明：增加 $k$ 条边，连接度数为奇数的节点，形成的图各个节点的度数都为偶数，在欧拉回路上增加的边一定不相邻，否则开始节点度数应该为偶数，然后在欧拉回路上去掉新增的边，即可划分为 $k$ 条简单道路。 ------- ![image-20230922150327070](https://notes.sjtu.edu.cn/uploads/upload_711406b192ba3e51a5a34ee6e0b89261.png) ### 哈密顿道路 哈密顿：每个顶点走一遍。 --------- **哈密顿 (H) 回路（道路）**：无向图 $G$ 的一条经过全部节点的初级回路（道路）。 - 要求 $V(G) \ge 3$. - 只需考虑简单图，因为重边和自环不起作用。 **哈密顿图**：具有 H 回路的图。$K_n$ 是哈密尔顿图？需要 $n \ge 3$. **哈密顿半图**：具有 H 道路而无 H 回路的图。 ![image-20231010210044639](https://notes.sjtu.edu.cn/uploads/upload_b544b3acb61dcf46c03bc918729f1991.png) $H$ 回路的判定很困难，没有发现充分必要条件，只有若干充分条件： - $d(v_i)+d(v_j) \ge n$，则存在 H 回路。 - 若简单图有 $H$ 回路当且仅当 $C(G)$ 有 H 回路。 - image-20231010212112228 ------- 引理： 设 $P:v_1,v_2,\cdots,v_l$ 是简单图 $G$ 中一条极长的初级道路，而且对于任意 $v_i,v_j$，$d(v_i)+d(v_j) \ge l$，则 $G$ 中一定存在经过节点 $v_1,v_2,\cdots,v_l$ 的 **初级回路**。 ![image-20231006101614724](https://notes.sjtu.edu.cn/uploads/upload_128fec5bc65e3dcda90186021f77728e.png) ----------- 定理：若简单图 $G$ 的任意两节点 $v_i$ 与 $v_j$ 之间恒有 $d(v_i)+d(v_j) \ge n-1$，则存在 **$H$ 道路**。 首先，$G$ 是连通图，假设有 2 个联通支，即是每个联通支是完全图， $$ d(v_i) \le n_1 -1, d(v_j) \le n_2 -1 \Rightarrow d(v_i)+d(v_j) \le n-2 有割点的连通图不是哈密顿图。 ![image-20231011103410771](https://notes.sjtu.edu.cn/uploads/upload_53e1d1191aa6883bc731b5e82cb52523.png) tips: 选择的点集贪心地考虑的话，要考虑度数大的，其次考虑和之前选的点尽量不相邻的。 ![image-20231011103931350](https://notes.sjtu.edu.cn/uploads/upload_eb3042a7e90afeca8c475ea257887289.png) 但是，对于 Peterson 图，都满足这个条件，但是也不是哈密顿图。 ----- 奇数个结点构成的二分图不是哈密顿图。 证:否则 H 圈是奇圈,而二部图无奇圈. ------ ![image-20231010210840048](https://notes.sjtu.edu.cn/uploads/upload_a946eb2af756ad5078cc124e1db02108.png) ## 树 ### 定义 - **树** 是不含回路的连通图 - 树必不含多重边和自环, 故是简单图 - 边称为树枝 - 度为1的结点称为树叶(leaf )或悬挂点 - 度大于等于2的结点称为分叉点 - **林** 是含回路的图 - 林可能不是连通的 - 林的每个连通支都是树- ------ **割边** 若 $G'=G-e$ 比 $G$ 的连通支数多, 则称 $e$ 是 $G$ 的割边. $e = (u,v)$ 是割边当且仅当 $e$ 不属于任何回路 $\Rightarrow$ **树中的边都是割边** ------ **树的等价定义** 设 $T$ 是节点数 $n \ge 2$ 的树，则下列性质互相等价： 1. $T$ 连通且无回路。 2. $T$ 连通且每条边都是割边。 3. $T$ 连通且有 $n-1$ 条边。 4. $T$ 有 $n-1$ 条边且无回路。 5. $T$ 的任意两节点之间有唯一道路。 6. $T$ 无回路，但是在任意两节点间加上一条边之后恰好有一个回路。 树是边数最少的连通图，也是边数最多的无回路图。 > 满足联通、无回路，$n-1$ 条边中任意两个条件的图是树。 ------- - 设树 $T$ 的节点数 $n \ge 2$，则 $T$ 中必然有树叶。 - 考虑节点度数。 - 考虑从任意节点 $v$ 出发沿边前进，走过的边不重复，则必然止步于某树叶。 - 设树 $T$ 的节点数 $n \ge 2$，则 $T$ 中至少有两个树叶（从一个树叶出发） - 若林 $F$ 中有 $n$ 个节点和 $k$ 个连通支，则 $F$ 有 $n-k$ 条边。 -------- **生成树** 定义: 如果 $T$ 是图 $G$ 的支撑子图, 而且是树, 则称 $T$ 是 $G$ 的支撑树或生成树。 图 $G$ 有支撑树当且仅当 $G$ 是连通的，若图 $G$ 本身不是树, 则其支撑树不唯一。 **余树** 图 $G$ 删掉生成树 $T$ 中各边后的子图。 - 余树不一定连通，也不一定无回路。 - 余树不一定是树，更不一定是生成树。 ### Huffman树 **二叉树** - 设 $T$ 是有向树，若 $T$ 中存在入度为 0 的节点 $v_0$，其余节点入度为 $1$，则称 $T$ 是以 $v_0$ 为根的外向树，或称 **根树**。 - 节点的出度最多为 2 的根树称为 **二叉树**； - 除了树叶外，其余结点的出度都是 2，称为 **完全二叉树**。 - 一棵高度为 $k$，并且具有 $2^k-1$ 个结点的二叉树，称为 **满二叉树**。 - 若二叉树的深度为 $h$，除了第 $h$ 层以外，其它各层的节点数都达到最大个数，第 $h$ 层的所有节点都连续集中在最左边，这就是 **完全二叉树**。 **赋权二叉树** - 赋予树叶 $v_i$ 一个正实数 $w_i$. - 带权路径总长度： $$ \mathrm{WPL}=\sum_i l_i w_i $$ **最优二叉树** 给定树叶数目及其权值，构造 WPL 最小的二叉树，称为 Huffman 树。 **Huffman 算法**：给定 $n$ 个带权树叶，构造最优二叉树。 1. 排序得 $w_{i1} \le w_{i2}\le \cdots \le w_{in}$. 2. 计算 $w_i=w_{i1}+w_{i2}$. 作为中间节点 $v_i$ 的权值，$v_i$ 左儿子是 $v_{i1}$，右儿子是 $v_{i2}$. $n-=1$. 3. 若 $n=1$，则输出，否则继续按 1. 排序。 **为什么是最优** 假定 $w_1\le w_2 \cdots \le w_n$，$l_i$ 为 $v_i$ 和根节点的距离，并且设 $T$ 是最优树。 - **$\boldsymbol{w_1}$ 离根最远**，如果存在 $w_k >w_1$ 而 $l_k >l_1$，交换 $w_k$ 和 $w_1$，得到更优的二叉树，矛盾。 - **$\boldsymbol{w_1}$ 必然有兄弟**，否则将 $w_1$ 赋值给树叶的父亲节点，可以得到更优的二叉树，其兄弟 $w_2$ 是序列中次小的权值。 - **递推** ![image-20231008144240093](https://notes.sjtu.edu.cn/uploads/upload_3275cda2cc2d2164affdb2b6714262c0.png) $n=2$ 时，是最优树，将分支收缩的过程相反进行展开，最后得到的 $T_n'$ 一定是最优二叉树。 最优的条件： $$ \mathrm{WPL}(T_n) \le \mathrm{WPL}(T'_n)\\ \mathrm{WPL}(T_{n-1}) \le \mathrm{WPL}(T'_{n-1}) $$ 由于，之前那张图对 $T_n$ 进行操作，$T_{n-1}$ 进行复原： $$ \mathrm{WPL}(T'_{n-1}) \le \mathrm{WPL}(T_n)-(w_1+w_2)\\ \mathrm{WPL}(T_{n-1}) \le \mathrm{WPL}(T'_{n})-(w_1+w_2) $$ 不等号放缩，可以得到： $$ \mathrm{WPL}(T_n) = \mathrm{WPL}(T'_n)\\ \mathrm{WPL}(T_{n-1}) = \mathrm{WPL}(T'_{n-1}) $$ 最优二叉树可能有很多种（交换左右子树），这里说明权值相等。 **Huffman 编码** - **数据的最小冗余编码问题** 使得编码序列的总长度最小； - **译码的唯一性原则** 任一字符的编码都不能是另一个字符的前缀。 **前缀码** 设 $\alpha=\alpha_1\alpha_2\cdots \alpha_{n-1}\alpha_n$ 是长度为 $n$ 的字符串，$\alpha_1\alpha_2\cdots\alpha_k$ 称为 $\alpha$ 的长度为 $k$ 的前缀，$k=1,2,\cdots,n-1$，若非空字符串 $\beta_1,\beta_2,\cdots,\beta_m$ 中任意两个互不为前缀，则称 $\{\beta_1,\cdots,\beta_m\}$ 为前缀码，只出现 0,1 的前缀码称为二元前缀码。 ### 最短树 - 求赋权连通图总长最小的支撑树； - 两种算法：Kruskal, Prim. #### Kruskal >将各边权重从小到大排序 >while(最小生成树的边数<=总节点数-1) >找到最小的边权重，他连接的两边节点作为起始点 >按从小到大的边权重顺序将节点加入图C中 定理：$T=(V,E')$ 是赋权连通图 $G=(V,E)$ 的最短树，当且仅当对于任意余树边 $e \in E-E'$，$E'+e$ 的回路 $C^e$ 满足： $$ w(e)\ge w(a),\mathrm{for~}\forall a\in C^e,a \not=e $$ 否则，$T \oplus (a,e)$ 得到的树 $T'$ 比 $T$ 更小。 #### Prim >需要先指定一个起始位置 >while(最小生成树的边数<=总节点数-1) >寻找该点边权重最小的节点加入图C中 >将图C看做一个整体，寻找C的所有边中权重最小的边，将所连点加入图C中 定理：假设 $V'$ 是赋权连通图 $G=(V,E)$ 的节点真子集，$e$ 是端点分别属于 $V'$ 和 $V-V'$ 的最短边，则 $G$ 中一定存在包含 $e$ 的最短树。 如果两点集之间连边为 $e'(\not=e)$，直接取 $T_0 \oplus(e,e')$ ## 匹配 引入：$m$ 项工作分配给 $n$ 个人去做，每人最多从事一项工作，每项工作最多由一人完成。 还可以在连边上做文章，比如可以限语言相通，一人领航一人驾驶等。 ### 二分图匹配 定义匹配：令 $M$ 是图 $G$ 的边子集，若 $M$ 中任意两条边都没有共同的顶点，则称 $M$ 是 $G$ 的一个 **匹配**。其中与 $M$ 的边相关联的顶点称为饱和点，否则称为非饱和点。 最大匹配时 $|M|$ 最大对应的匹配。 给定了 $G$ 的一个匹配 $M$，$G$ 中属于 $M$ 和不属于 $M$ 的边交替出现的道路称为 **交互道路**，构成回路的交互道路称为 **交互回路**。 设 $P$ 是 $G$ 中关于匹配 $M$ 的一条交互道路，如果 $P$ 的两个端点是关于 $M$ 的非饱和点（可以连出去新的边） ，则它称为 **可增广道路**。 定理：$M$ 是 $G$ 的最大匹配当且仅当 $G$ 中不存在关于 $M$ 的可增广道路。 $\Rightarrow$ 使用反证法即可。 $\Leftarrow$ 转化为：$G$ 中不存在关于 $M$ 的可增广道路时，$M$ 是 $G$ 的最大匹配。则需要证明当 $M$ 不是 $G$ 的最大匹配时一定存在可增广道路。分析 $G'=M' \oplus M$，$G'$ 联通支中不可能出现度数大于 3 的节点，此时节点连出的边中存在两个同时属于 $M'$ 或 $M$. 因此，联通支只有三种情况： 1. 孤立顶点，当 $(v_i,v_j) \in M' \cap M$ 时会出现孤立点 $v_i$ 和 $v_j$，代表边相互抵消； 2. 初级回路，此时 $M$ 的边和 $M'$ 的边交替出现，也相当于出现次数相等； 3. 初级道路，$|M'| \not= |M|$，只有可能在初级道路上两者出现次数不等，此时必定存在 $M'$ 关于 $M$ 的可增广交互道路。 ![image-20231017200547069](https://notes.sjtu.edu.cn/uploads/upload_6a8ee483416c1f45c0fe40cb2cc3c213.png) 注意 $x_4,x_5$ 也算一条可增广交互道路。 ### 完全匹配 $|M|=|X|$，称为完全匹配，$|M|=|X|=|Y|$，称为完美匹配。 Hall 定理给出了判别完全匹配的条件： **证明**：$X$ 到 $Y$ 存在完全匹配的充要条件是对于 $X$ 的任意子集 $A$，恒有 $|\Gamma(A)|\ge |A|$. 若存在 $|\Gamma(A)| < |A|$，则 $A$ 连出的边无法覆盖，因此，不存在完美匹配。 若不存在完全匹配，则设 $x_0$ 没有匹配上，则 $x_0$ 连到的节点一定被匹配了，而且不存在增广路，设增广路左边节点的集合为 $X_1$，右边节点的集合为 $Y_1$，根据匹配的性质，$Y_1$ 的顶点与 $X_1-x_0$ 的顶点存在一一对应，因此 $|X_1|=1+|Y_1| > |\Gamma(X_1)|$. 矛盾。 ![image-20231017215730445](https://notes.sjtu.edu.cn/uploads/upload_b07811d42099a1ca8fe9ad8fc46f2ed3.png) **定理** 在二分图 $G=(X,Y,E)$ 中，$X$ 到 $Y$ 最大匹配的边数是 $|X|-\delta(G)$，其中 $\delta(G)=\max_{A \subseteq x} \delta(A)$，$\delta (A)=|A|-|\Gamma(A)|,\delta(A)\ge 0$. ### 二分图最大匹配的König定理 利用最小割最大流定理的证明：原点向左边连流量为 $1$ 的边，然后原来的边流量为 $+\infin$，右边向汇点连流量 $1$ 的边。最大流对应最大匹配，最小割割掉的边和点对应，割掉之后，相当于断开这个点相连的所有边。 最大独立集是最小点覆盖的补集，如果补集中有两点相连，说明这条边没有在最小点覆盖中覆盖到。 ## 网络流 ### jyy 的引入：求不相交路径个数 我们考虑一个这样的问题，假设图 $G$ 节点可以分为 $S,T$ 两个集合，其中 $S$ 没有向 $T$ 连任何一条边，若 $s \in S,t \in T$，则从 $s$ 到 $t$ 没有路径。我们再考虑，若用 $\operatorname{Cut}(S,T)$ 表示从 $S$ 向 $T$ 连的边数目，给定 $s,t$，最小割定义为： $$ \operatorname{MinCut}=\min_{S,T;s\in S,t\in T} \operatorname{Cut}(S,T) $$ 最小割对应的 $S,T$ 集合称为 $S^*$ 和 $T^*$. 再考虑从 $s$ 到 $t$ 的最多边不重复路径个数 $\operatorname{MaxRoute}$，可以发现对于每一条路径，由于其从 $S^*$ 中的节点 $s$ 出发，到 $T^*$ 中的节点 $t$ 结束，因此，路径中必然存在一条边，连接了 $u\in S^*,v \in T^*$，而最多有 $\operatorname{MinCut}$ 这么多的这样的边，因此，可得： $$ \operatorname{MaxRoute} \le \operatorname{MinCut} $$ 再考虑怎么证明等号可以取到，这里，我们考虑朴素的贪心：看到了一条路径，就取这条路径。 ![image-20231104110703271](https://notes.sjtu.edu.cn/uploads/upload_d43989981a279e9db8efa3bafad6254f.png) - 假设我们第一次取 $1\to 2 \to 4 \to 6$，那么第二次取 $1\to 3\to 4\to 5\to 6$，万事大吉。 - 但是我们如果第一次取 $1\to2\to3\to4\to6$，导致第二次无路可走，如何避免这种情况发生？ 类似于二分图最大匹配，我们采用反悔的机制。再考虑二分图最大匹配的证明，证明里面使用了对称差，其本质是一种加法，因此可以考虑给正向边和反向边都赋予权值，然后我们求出来路径里面，正向边和反向边是可以抵消的。 一开始，我们给所有正向的边赋予权值 1，所有反向的边赋予权值 0，假设我们决定取这条边，则正向赋予 0，反向赋予 1，代表我们可以反悔，通过后来反向取这条边，来不取这条边。 举例，假设我们先取了 $1\to2\to3\to4\to6$，边权如下： ![image-20231104111057901](https://notes.sjtu.edu.cn/uploads/upload_b0a6b544fdc80e7ce096287878fcc9c3.png) 容易发现存在路径 $1 \to 3\to 2\to 4\to 5\to 6$，因此，继续取这条路径。 ![image-20231104111306929](https://notes.sjtu.edu.cn/uploads/upload_e253e0b4bf2be2d976bb0c608fab0156.png) 这两条路径进行抵消，可以得到 $1\to 2 \to 4 \to 6$，$1\to 3\to 4\to 5\to 6$。 再考虑一条新路径和原路径抵消之后为什么会多出来一条路径，这个其实和二分图增广路的思想差不多，画个图比较容易理解。 再考虑为什么算法结束的时候，一定能找到 $\operatorname{MinCut}$ 条路径，假设算法结束时，找到了 $m$ 条路径。 - 由之前的推导，$m \le \operatorname{MaxRoute} \le \operatorname{MinCut}$. - $m$ 条路径对应了原图最小割，$m\ge \operatorname{MinCut}$. 因此，$m = \operatorname{MaxRoute} = \operatorname{MinCut}$. 利用重边，这种方法可以推广到边权为整数的情况，进而推广到非整数的情况。 ### 最大流最小割定理 可以用这种方法理解网络流中的对偶性，即最大流=最小割，还可以用线性规划的方法理解： 假设有 $k$ 种可能的路径 $p_1,\cdots,p_k$，其对应的流量为 $f_1,\cdots,f_k$，假设有 $m$ 条边 $e_1,\cdots,e_m$，由每条边流量的限制： $$ \forall e_j,\sum_{\forall i,e_j \in p_i} f_k \le C(e_j)\\ \max \sum_{i=1}^k f_i $$ 转化为对偶形式，假设第 $j$ 个不等式取 $\lambda_j$ 倍，则： $$ \forall p_i,\sum_{\forall j, e_j \in p_i}\lambda_j \ge 1\\ \min \sum_{i=1}^m C(e_j)\lambda_j $$ 这其实就对应了最小割，表示任意一条路径都不能通过。 容易发现这样的线性规划 $k$ 比较大，参数量多，求解困难，但是相对容易理解。我们还可以将流过边的流量设为参数，发现源点流出的、汇点汇入的时网络的总流量，并且满足节点没有流量残余，即最大流： $$ \begin{align*} \max \ & v=\sum _ {e\text{ out of } s}f(e) = \sum _ {e\text{ into } t}f(e)\\s.t. \sum_{e\text{ into } v} f(e) - \sum_{e\text{ out of } v} f(e) &=0, \forall v\in V-{s,t} \\ f(e)&\le c _ e,\forall e\in E\\ f(e)&\ge 0,\forall e\in E\\ \end{align*} $$ 可得它的对偶问题为： $$ \begin{align*} \min \ & \sum_{e\in E} c_ey_e\\ \text{s.t.}\ u_i-u_j+y_e &\ge 0, e=(i,j)\in E\\ -u_s+u_t&=1\\ y_e&\ge 0 \end{align*} $$ 对应了最小割。 ### E-K 算法 ```cpp int dfs(int c, int t, int f) { if (c == t) { return f; } used[c] = true; for (int i = 0; i < G[c].size(); ++ i) { Edge &e = G[c][i]; if (!used[e.to] && e.cap > 0) { int d = dfs(e.to, t, min(f, e.cap)); if (d > 0) { e.cap -= d; G[e.to][e.rev].cap += d; return d; } } } return 0; } int max_flow(int s, int t) { int flow = 0; int cnt = 0; for (;;) { memset(used, 0, sizeof(used)); int f = dfs(s, t, INF); cnt += 1; if (f == 0) { cout << cnt << endl; return flow; } flow += f; } } ``` 效率低的原因，是因为一次只找一条增广路。 ### Dinic 算法 核心思想在于每次找多条增广路。 ```cpp bool BFS() { memset(vis, 0, sizeof(vis)); queue Q; Q.push(s); d[s] = 0; vis[s] = 1; while (!Q.empty()) { int x = Q.front(); Q.pop(); for (int i = 0; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (!vis[e.to] && e.cap > e.flow) { vis[e.to] = 1; d[e.to] = d[x] + 1; Q.push(e.to); } } } return vis[t]; } ``` BFS 算法求出有余量的，构建分层图- ```cpp int DFS(int x, int a) { if (x == t || a == 0) return a; int flow = 0; for (int& i = cur[x]; i < G[x].size(); i++) { Edge& e = edges[G[x][i]]; if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) { e.flow += f; edges[G[x][i] ^ 1].flow -= f; flow += f; a -= f; if (a == 0) break; } } return flow; } ``` 遍历分层图上的后继节点，只要当前可用流量能够承受，就继续分叉，这样可以一次找多条增广路。 ### 平面图转对偶图 如果图 $G$ 是一张平面图，还可以通过转为对偶图的方法，用最短路求最小割。 ![image-20231104131220503](https://notes.sjtu.edu.cn/uploads/upload_7d4c150301a2dd490ea4a7b8dd7f2207.png) 如图，如果源点是橙色的点，汇点是绿色的点，建立对偶图，在源-汇连线左手侧的边界边连到最短路的超级源点，右手侧的边界边连到最短路的超级汇点，最短路即对应最小割。 发现这样平面图的节点数和边数都是 $m$ 量级，最短路时间复杂度 $\mathcal O(m \log m)$，而原图网络流用 Dinic 算法复杂度 $\mathcal O(mn^2)$，可见优化程度比较大。 ### 最小费用最大流 每条边新增单位流量的费用 $w(e)$，满足斜对称性，即 $e$ 反向，费用取相反数，要求在最大化最大流的情况下，最小化： $$ \sum_{e} f(e) \times w(e) $$ 思路是每次寻找单位流量费用最小的增广路：$w$ 的最短路。 ```cpp struct qxx { int nex, t, v, c; }; qxx e[M]; int h[N], cnt = 1; void add_path(int f, int t, int v, int c) { e[++cnt] = (qxx){h[f], t, v, c}, h[f] = cnt; } void add_flow(int f, int t, int v, int c) { add_path(f, t, v, c); add_path(t, f, 0, -c); } int dis[N], pre[N], incf[N]; bool vis[N]; bool spfa() { memset(dis, 0x3f, sizeof(dis)); queue q; q.push(s), dis[s] = 0, incf[s] = INF, incf[t] = 0; while (q.size()) { int u = q.front(); q.pop(); vis[u] = 0; for (int i = h[u]; i; i = e[i].nex) { const int &v = e[i].t, &w = e[i].v, &c = e[i].c; if (!w || dis[v] <= dis[u] + c) continue; dis[v] = dis[u] + c, incf[v] = min(w, incf[u]), pre[v] = i; // 记录 SPFA 路径 if (!vis[v]) q.push(v), vis[v] = 1; } } return incf[t]; } int maxflow, mincost; void update() { maxflow += incf[t]; for (int u = t; u != s; u = e[pre[u] ^ 1].t) { e[pre[u]].v -= incf[t], e[pre[u] ^ 1].v += incf[t]; mincost += incf[t] * e[pre[u]].c; } } // 调用：while(spfa())update(); ``` ## 习题 ### 2.1 ![image-20231010192103651](https://notes.sjtu.edu.cn/uploads/upload_8303a51864fbf5ddfba9f85a2583bb9e.png) **法一**： 利用不等式： $$ C_{n_1+n_2-1}^2-(C_{n_1}^2+C_{n_2}^2)=(n_1-1)(n_2-1) \ge 0\\ \Rightarrow C_{n_1+n_2-1}^2 \ge C_{n_1}^2+C_{n_2}^2 $$ 因此，若 $k$ 个联通支的节点数分别为 $n_i$，$\sum n_i=n$，则： $$ \sum C_{n_i}^2 \le C_{\sum n_i -k}^2=C_{n-k}^2 = \frac{1}{2}(n-k+1)(n-k) $$ **法二**： 数学归纳法。 - 显然 $n=1$ 时成立。 - 假设 $n$ 时成立，对于 $n+1$ 时，去掉多余的一个点，形成的连通块数量 $\ge k$，则新图的边数： $$ m' \le \frac{1}{2} (n-k+1)(n-k) $$ 然后再考虑多余的一个点，至多连出 $n-k+1$ 条边，因为只能连到一个连通块中，而其最大大小为 $n-k+1$ $$ m \le \frac{1}{2}(n-k+1)(n-k)+n-k+1=\frac{1}{2}(n-k+1)(n-k+2) $$ 再证明构造上届能取到…… ### 2.2 ![image-20231010193013839](https://notes.sjtu.edu.cn/uploads/upload_4980e252dd8737b34d3b139cae9d2f9c.png) 假设 $G$ 和 $\overline{G}$ 都不是连通图，$G$ 分为 $V_1,V_2$ 两个点集，$V_1 \cup V_2=V$，而且 $V_1,V_2$ 间没有连边，$\overline{G}$ 分为 $V_1'$ 和 $V_2'$，假设 $V_1 \cap V_1' \not=\emptyset$，则点集 $V_1\cap V_1',V_2 \cap V_2'$ 既在 $G$ 中无连边，又在 $\overline{G}$ 中无连边，矛盾。 ### 2.3 ![image-20231010193349568](https://notes.sjtu.edu.cn/uploads/upload_e82497bfda472c93ef29cb597c6e4947.png) 若存在两个不相交的道路 $l_1,l_2$，则必定存在 $u\in l_1,v\in l_2$，且 $u,v$ 间存在一条道路与 $l_1,l_2$ 均不相交（否则违反了连通的条件） ![image-20231010193550312](https://notes.sjtu.edu.cn/uploads/upload_a41056ea63a5d0e137dd4e7140cd4aac.png) $$ a+b=c+d=l_m, a+e+d \le l_m,c+e+b \le l_m \Rightarrow e \le 0 $$ 显然矛盾。 ### 2.4 ![image-20231010193652979](https://notes.sjtu.edu.cn/uploads/upload_554bd8488be2c02dcf3b04b9521e47dc.png) **带弦回路的引理**：如果简单图 $G$ 的一条极长初级道路的一个端点的度数 $\ge 3$，则 $G$ 存在带弦回路。 假设 $d(a_1) \ge3$ 且 $a_1$ 与 $a_i,a_j$ 相连，且 $i=2(k + 1) − 3 − 2 = 2k − 3$的图，根据归纳假设，$G − v$含有带弦回路，那么$G$也必含有带弦回路。 tips: 和边数相关的问题，常常使用数学归纳法。 ### 2.5 ![image-20231010194815313](https://notes.sjtu.edu.cn/uploads/upload_7e425d5925970f60254dc08fbc20bdae.png) 极端情况，当 $n$ 为偶数时，分为两个部分，节点数都为 $n/2$，然后互相连边。 $$ (d(a)-1)+(d(b)-1) \le n-2 \Rightarrow d(a)+d(b)\le n $$ 对于每一条边都如此求和，每个顶点的度数被求和的次数恰好为每个顶点的度数，因此： $$ \sum d^2(v_i) \le mn $$ 由柯西不等式： $$ mn \ge \sum d^2(v_i) \\ mn^2 \ge (\sum 1 )(\sum d^2(v_i)) \ge (\sum d(v_i))^2= 4m^2 $$ 因此，$\displaystyle m \le \frac{n^2}{4}$. ### 2.7 ![image-20231010200513155](https://notes.sjtu.edu.cn/uploads/upload_9261364b8dfa8ba711269ad1671fea1c.png) 数学归纳法。 ### 2.17 ![image-20231010201025227](https://notes.sjtu.edu.cn/uploads/upload_3ae8912b178c1edadd91ab31810cf878.png) 考虑 $H$ 道路组成了子图 $G'$，则 $G'-S$ 的连通支数 $t'\le |S|+1$ 再考虑到是导出子图，因此 $t\le t'$。 ### 2.21 ![image-20231010201713716](https://notes.sjtu.edu.cn/uploads/upload_5391cf44bb76966cca37033acd880229.png) todo ### 2.25 ![image-20231010203552388](https://notes.sjtu.edu.cn/uploads/upload_c7518bf234e4379a72fb3ff5bce7f58c.png) 这个好做…… ### 2.29 ![image-20231010204040866](https://notes.sjtu.edu.cn/uploads/upload_5c78d8b546e49ec9cbe8471946e1777f.png) 运用缩点的思想 数学归纳法？ ### 6.21 ![image-20231010213019069](https://notes.sjtu.edu.cn/uploads/upload_0228bf0d9d131afbc71af41a0e415f8a.png) 同构图判定： $$ m+m'=\frac{n(n-1)}{2} \Rightarrow m=\frac{n(n-1)}{4} $$ > 这里就能看出 $n,(n-1)$ 其中一个必定是 4 的倍数。 顶点度数，$\ge0$，重排序列相同： $$ 3,3,3,3\Rightarrow 1,1,2,2+2,2,1,1\\ 4,4,4,4,4 \Rightarrow 2,2,2,2,2+2,2,2,2,2 \quad 1,1,2,3,3+3,3,2,1,1 $$ ![image-20231010213433119](https://notes.sjtu.edu.cn/uploads/upload_22845d35f11eda665899c3792222d095.png) 如果有向，则顶点度数序列变为： $$ 2,2,2;2,2,2 \Rightarrow 1,1,1;1,1,1 \quad 1,0,2;0,1,2\cdots $$ ![image-20231010213705428](https://notes.sjtu.edu.cn/uploads/upload_8af980773b0ba683509a02334c2473f0.png) 这时，对 $n$ 没什么限制。 ### 6.40 ![image-20231010213933442](https://notes.sjtu.edu.cn/uploads/upload_66e556e0fa00e76d8f9803cda8db8f96.png) ### 06-12 一棵树有 $n_1$ 个节点的度数为 $1$，$n_2$ 个节点的度数为 $2$，……，$n_{k-1}$ 个节点的度数为 $k-1$，节点最大的度为 $k$，问这样的节点一共多少个： $$ \sum_{i=1}^k in_i = 2\left(\sum_{i=1}^k n_k-1\right) $$ 因此， $$ \sum_{i=1}^{k-1} (i-2)n_i +2=2n_k-kn_k $$ 因此： $$ n_k= \frac{2+\sum_{i=1}^{k-1}(i-2)n_i}{2-k} $$ 和 $n_2$ 无关。 原因是这样相当于增加链的长度，无影响。 ### 10-七 设 $G$ 是一个连通图，其中 $T$ 是 $G$ 的一棵生成树，设 $e$ 是 $G-T$ 中的任意有一条边，证明：$T+e$ 中有且仅有一个圈（初级回路）。 设 $e=(u,v)$, - 圈 $C$ 的存在性：由于 $T$ 中从 $u$ 到 $v$ 存在一条初级回路 $P$，所以加上边 $e$ 后，得到的 $P+e$ 一定是一个圈。 - 圈 $C$ 的唯一性：由于 $T$ 一开始是一棵树，而加上 $e$ 后产生回路，所以产生的回路一定包含 $e$，不妨设为 $P_1+e$ 和 $P_2+e$，则 $P_1+P_2$ 构成回路。