课程简介

离散数学 研究对象：离散个体以及结构关系

图论与代数结构 的书还讨论了 平面图与图的着色、图的匹配问题、网络流、抽象代数的内容

图的基本概念

主要复习：

• 图的基本概念

  • 有向图的度=入度+出度

  • 支撑子图/生成子图 v.s. 导出子图；

  • 图的代数表示：What's 关联矩阵（$n\times m$$n\times m$ 的矩阵）、边列表和正向表；

  • 证明方法：反证法，数学归纳法，直接证明构造法。

  • 含有 $n$$n$ 个结点的简单图一共有 $2^{n(n-1)/2}$$2^{n(n-1)/2}$ 个。

• 道路与回路

  • 道路可以表示为 $v,e,v,e,\cdots ,v$$v,e,v,e,\cdots,v$，回路在道路的基础上，要求首尾节点相同。

  • 如果 $P$$P$ or $C$$C$ 中没有重复出现的边, 称之为 简单道路 或简单回路, 若其中结点也不重复, 又称之为 初级道路 或初级回路。

  • 区别欧拉回路（每条边经过一遍）和哈密顿回路（每个点经过一遍）

  • 完全图哈密顿回路的个数 ${\displaystyle \frac{1}{2}(n-1)!}$$\displaystyle \frac{1}{2}(n-1)!$.

  • Peterson 图：存在哈密顿道路而无哈密顿回路；

  • 哈密顿道路判定的结论：

    • $\mathrm{\forall }i,j,d(v_i)+d(v_j)\ge n-1$$\forall i,j , d(v_i)+d(v_j) \ge n-1$ 证明：先证明联通，然后再取极大路径，先构造回路，然后再扩展成更长的道路，直到长度 $l=n$$l=n$.

    • $n$$n$ 个人中，两个人合起来都认识其余 $n-2$$n-2$ 个人。证明：若 $v_i,v_j$$v_i,v_j$ 互相认识，则 $d(v_i)+d(v_j)\ge n$$d(v_i)+d(v_j) \ge n$；否则一定认识同一个人，出现重复，$d(v_i)+d(v_j)\ge n-1$$d(v_i)+d(v_j) \ge n-1$.

    • 也可以这么证明：取极长回路，一定会包含所有节点，如果不包含 $v_i$$v_i$，首尾节点其中一个一定和 $v_i$$v_i$ 相连。

  • 哈密顿回路判定的结论：

    • $\mathrm{\forall }i,j,d(v_i)+d(v_j)\ge n$$\forall i,j, d(v_i)+d(v_j) \ge n$ 证明：运用上面的结论得到哈密顿道路，然后再扩展成为回路。

    • $m\ge C_{n-1}^2+2$$m\ge C_{n-1}^2 +2$ 运用上面的结论证明。

  • 不存在哈密顿回路的判定：

    • $G-V$$G-V$ 的导出子图联通支数大于 $|V|$$|V|$.

    • 可以被画作二分图，而有奇数个节点。可以被画作二分图，但是两个点集的大小不相同。

  • 不存在哈密顿道路的判定：

    • $G-V$$G-V$ 的导出子图联通支数大于 $|V|+1$$|V|+1$.

  • 闭合图：若简单图有不相邻节点 $v_i$$v_i$ 与 $v_j$$v_j$ 满足 $d(v_i)+d(v_j)\ge n$$d(v_i)+d(v_j) \ge n$，则 $G$$G$ 存在 H 回路当且仅当 $G+(v_i,v_j)$$G+(v_i,v_j)$ 存在 H 回路。若加边前不存在，则必然存在 H 道路，但是因为不能构造初级回路所以 $d(v_1)+d(v_l)\le n-1<n$$d(v_1)+d(v_l )\le n-1 <n$. 矛盾，得证。

• 树

  • Huffman 树：$n$$n$ 个叶子 $2n-1$$2n-1$ 个节点，没有正度为 1 的节点，前缀码的概念。

图的概念

图 $G$$G$ 是一个二元组：$G=(V,E)$$G=(V,E)$.

• $V$$V$ 代表非空节点(vertex)集合。

• $E$$E$ 表示边(edge)的集合，每条边与 $V$$V$ 中的两个节点(可相同)相关联。

对任一图 $G$$G$，用 $V(G),E(G)$$V(G),E(G)$ 表示节点集合和边集合。

图的分类

• 无限图：节点集或者边集是无穷集合。

• 有限图：节点集或者边集均是有限集合。我们只讨论有限图。

  • 节点集 $V(G)=\{v_1,v_2,\cdots ,v_n\},|V(G)|=n$$V(G)=\{v_1,v_2,\cdots,v_n\},|V(G)|=n$

  • 边集 $E(G)=\{e_1,e_2,\cdots ,e_m\},|E(G)|=m$$E(G)=\{e_1,e_2,\cdots,e_m\},|E(G)|=m$

• 无向图：所有的边是无向边：$e_k=\text{无}\text{序}\text{的}(v_i,v_j)$$e_k=无序的(v_i,v_j)$，邻点集 $\mathrm{\Gamma }(v_i)=\{v_j\mid (v_i,v_j)\in E\}$$\Gamma(v_i)=\{v_j\mid(v_i,v_j) \in E\}$.

• 有向图：所有的边是有向边：$e_k=\text{有}\text{序}\text{的}(v_i,v_j),⟨v_i,v_j⟩$$e_k=有序的(v_i,v_j),\langle v_i,v_j\rangle$，${\mathrm{\Gamma }}^{+}(v_i)=\{v_j\mid (v_i,v_j)\in E\},{\mathrm{\Gamma }}^{-}(v_i)=\{v_j\mid (v_j,v_i)\in E\}$$\Gamma^+(v_i)=\{v_j\mid(v_i,v_j) \in E\},\Gamma^-(v_i)=\{v_j\mid(v_j,v_i) \in E\}$.

  $\mathrm{\Gamma }(v_i)={\mathrm{\Gamma }}^{+}(v_i)\cup {\mathrm{\Gamma }}^{-}(v_i)$$\Gamma(v_i)=\Gamma^+(v_i)\cup\Gamma^-(v_i)$.

• 混合图：既有无向边又有有向边。

自环和重边

• 自环：$e_k=(v_i,v_i)$$e_k=(v_i,v_i)$.

• 重边：两个节点有多条边。

• 简单图 无自环无重边的无向图。

• 空图 有点无边的图。

• 完全图 任意两节点之间都有边的简单图。$K_n$$K_n$

节点的度

• 定义：与节点 $v$$v$ 关联的边数，记作 $d(v)$$d(v)$，有向图有 $d^{-}(v)$$d^-(v)$ 和 $d^{+}(v)$$d^+(v)$.

• $K_n$$K_n$ 的边数 ${\displaystyle \frac{1}{2}n(n-1)}$$\displaystyle \frac{1}{2}n(n-1)$.

• 握手定理：对于 $G(V,E),|E|=m$$G(V,E),|E|=m$，则 ${\displaystyle \sum _{v\in V(G)}d(v)=2m}$$\displaystyle \sum_{v \in V(G)} d(v)=2m$.

  • $\Rightarrow$$\Rightarrow$ 度为奇数的节点一定是偶数个。因为 ${\displaystyle \sum _{v\in V_o(G)}d(v)+\sum _{v\in V_e(G)}d(v)=2m}$$\displaystyle \sum_{v \in V_o(G)} d(v)+\sum_{v \in V_e(G)} d(v)=2m$.

  • $\Rightarrow$$\Rightarrow$ 有向图中正度之和和负度之和相等。

  • $\Rightarrow$$\Rightarrow$ 非空简单图中一定存在度相同的节点。

赋权图

• 定义：对每条边 $e_k$$e_k$ 都赋予权值 $w_k$$w_k$ 作为边的权值，则称 $G$$G$ 是赋权图。

子图

• 定义：给定 $G=(V,E)$$G=(V,E)$，若 $G^{\prime }=(V^{\prime },E^{\prime })$$G'=(V',E')$，满足 $V^{\prime }\subseteq V,E^{\prime }\subseteq E$$V' \subseteq V, E' \subseteq E$，则称 $G^{\prime }$$G'$ 是 $G$$G$ 的子图，称为 $G^{\prime }\subseteq G$$G' \subseteq G$.

• 如果 $V^{\prime }=V$$V'=V$，则称 $G^{\prime }$$G'$ 是 $G$$G$ 的支撑子图或者生成子图。

• 如果 $V^{\prime }\subseteq V$$V' \subseteq V$，且对于任意的 $v_i,v_j\in V^{\prime }$$v_i,v_j \in V'$，若 $e_k=(v_i,v_j)\in E$$e_k=(v_i,v_j) \in E$，则 $e_k\in E^{\prime }$$e_k\in E'$，则称 $G^{\prime }$$G'$ 是 $G$$G$ 的导出子图。

• $G$$G$ 自身满足两个定义。

记忆：生成子图对节点集有要求，导出子图对边有要求。

图的运算

交 $G_1\cap G_2=(V_1\cap V_2,E_1\cap E_2)$$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 \cup G_2=(V_1\cup V_2,E_1 \cup E_2)$、差（$G_1-G_2=(V_1,E_1-E_2)$$G_1-G_2=(V_1,E_1-E_2)$，如果出现孤立点，删掉）、补（$\overline{G_1}=K_n-G_1$$\overline{G_1}=K_n-G_1$）.

对称差（$G_1\oplus G_2=(G_1-G_2)\cup (G_2-G_1)$$G_1 \oplus G_2 = (G_1-G_2) \cup (G_2-G_1)$）

图的运算

• 删点 $G-v$$G-v$（还要删去连边）

图的同构

定义：给定图 $G_1=(V_1,E_1)$$G_1=(V_1,E_1)$ 以及图 $G_2=(V_2,E_2)$$G_2=(V_2,E_2)$，如果在 $V_1$$V_1$ 和 $V_2$$V_2$ 之间存在双射使得

则 $G_1$$G_1$ 和 $G_2$$G_2$ 同构，记为 $G_1\cong G_2$$G_1 \cong G_2$。

必要条件：

• $|V(G_1)|=|V(G_2)||E(G_1)|=|E(G_2)|$$|V(G_1)|=|V(G_2)| \quad |E(G_1)| = |E(G_2)|$.

• $G_1$$G_1$ 和 $G_2$$G_2$ 节点度的非增序列相同。

• $G_1$$G_1$ 和 $G_2$$G_2$ 的导出子图相同。

Peterson 图。

Ramsey 定理

对于红色 $K_s$$K_s$ 或者蓝色 $K_t$$K_t$，一定能够找一个最小的 $n$$n$，使得若对完全图 $K_n$$K_n$ 中的所有线段染红色或蓝色，一定会出现红色 $K_s$$K_s$ 或者蓝色 $K_t$$K_t$.

• $R(2,n)=n$$R(2,n)=n$.

• $R(3,3)=6$$R(3,3)=6$（鸽笼原理）

• $R(m,n)=R(n,m)$$R(m,n)=R(n,m)$.

• $R(s,t)\le R(s-1,t)+R(s,t-1)(s,t\in {\mathbb{Z}}^{\ast },s,t>2)$$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)$$R(s-1,t)+R(s,t-1)$ 个人……

代数表示

邻接矩阵 (adjacency matrix)

无向图的邻接矩阵是对称矩阵；无向简单图邻接矩阵的第 $i$$i$ 行之和为结点 $v_i$$v_i$ 的度。

权矩阵

关联矩阵 (incidence matrix)

有向图 $G=(V,E)$$G=(V,E)$ 的关联矩阵是一个 $n\times m$$n \times m$ 矩阵 $B$$B$，其元素为：

• 每列只有两个 $1,-1$$1,-1$. $1$$1$ 代表出，$-1$$-1$ 代表入；

• 第 $i$$i$ 行 1 的个数为 $d^{+}(v_i)$$d^+(v_i)$，-1 的个数为 $d^{-}(v_i)$$d^-(v_i)$。

• 可以表示重边，不能表示自环。

图的矩阵表示：

• 矩阵表示法唯一、直观。

• 不能表示重边或者自环。

• 需要较大的存储空间。

边列表 对于每条边 $e_k=(v_i,v_j)$$e_k=(v_i,v_j)$，有：

正向表 有向图用 $n+1$$n+1$ 维向量 $A$$A$ 和 $m$$m$ 维向量 $B$$B$ 来表示。

• $A(i)$$A(i)$ 表示存储 $v_i$$v_i$ 的第一个直接后继在 $B$$B$ 中的地址，$A(n+1)=m+1$$A(n+1)=m+1$.

• $B$$B$ 存储 $m$$m$ 个直接后继节点的编号。

• $d^{+}(v_i)=A(i+1)-A(i)$$d^+(v_i)=A(i+1)-A(i)$.

• ${\displaystyle A(i)=\sum _{j=1}^{i-1}{d}^{+}(v_j)+1}$$\displaystyle A(i)=\sum_{j=1}^{i-1} d^+(v_j)+1$.

• 从 $B(A(i))$$B(A(i))$ 到 $B(A(i+1)-1)$$B(A(i+1)-1)$ 的任意一个值，都是 $v_i$$v_i$ 的直接后继。

但是插入删除操作复杂度高。

邻接表

道路与回路

道路与回路

有向道路 有向图 $G$$G$ 中边序列 $P=(e_{i_1},e_{i_2},\cdots ,e_{i_q})$$P=(e_{i_1},e_{i_2},\cdots,e_{i_q})$，其中 $e_{i_j}=(v_k,v_i)$$e_{i_j}=(v_k,v_i)$ 满足 $v_k$$v_k$ 是 $e_{i_{j-1}}$$e_{i_{j-1}}$ 的终点，$v_i$$v_i$ 是 $e_{i_{j+1}}$$e_{i_{j+1}}$ 的起始点。

有向回路 $e_{i_q}$$e_{i_q}$ 的终点也是 $e_{i_1}$$e_{i_1}$ 的始点。

道路/链 无向图 $G=(V,E)$$G=(V, E)$ 中, 若点边交替序列 $P=(v_{i1},e_{i1},v_{i2},e_{i2},\cdots ,e_{iq-1},v_{iq})$$P=\left(v_{i 1}, e_{i 1}, v_{i 2}, e_{i 2}, \cdots, e_{i q-1}, v_{i q}\right)$ 满足 $v_{ik},v_{ik+1}$$v_{i k}, v_{i k+1}$ 是 $e_{ik}$$e_{i k}$ 的两个端点, 则称 $P$$P$ 是 $G$$G$ 中的一条链, 或道路。如果 $v_{iq}=v_{i1}$$v_{i q}=v_{i 1}$, 则称 $P$$P$ 是 $G$$G$ 中的一个圈, 或回路。

一个点可以成为道路，但是不能成为回路。

如果 $P$$P$ 中没有重复出现的边, 称之为 简单道路 或简单回路, 若其中结点也不重复, 又称之为 初级道路 或初级回路。

回路/圈

极长路径/初级道路 $P$$P$ 是一条初级道路（点不重复），始点和终点都不与 $P$$P$ 外的顶点相邻。

扩大初级道路法 求极长路径。

弦 设 $C$$C$ 为简单图 $G$$G$ 中含节点数大于 3 的一个初级回路，如果结点 $v_i$$v_i$ 和 $v_j$$v_j$ 在 $C$$C$ 中不相邻，而边 $(v_i,v_j)\in E(G)$$(v_i,v_j) \in E(G)$，则 $(v_i,v_j)$$(v_i,v_j)$ 是 $C$$C$ 的一条弦。

联通性

• 若无向图 $G$$G$ 的任意两个节点之间都存在道路，则 $G$$G$ 是联通的。

• 对于有向图 $G$$G$，若去掉方向，是联通的，则称为(弱)联通。

• 若 $G$$G$ 的联通子图 $H$$H$ 不是 $G$$G$ 其它任何联通子图的真子图，则称 $H$$H$ 是 $G$$G$ 的 极大联通子图，或称为 联通支。

• 设 $v$$v$ 是 $G$$G$ 的一个结点，若 $G-v$$G-v$ 的联通支数比 $G$$G$ 多，则称 $v$$v$ 是 $G$$G$ 的一个割点。

• 若 $G$$G$ 是简单图，试证明 ${\displaystyle m>\frac{1}{2}(n-1)(n-2)}$$\displaystyle m>\frac{1}{2}(n-1)(n-2)$ 时，$G$$G$ 是连通图。若分为两个部分……

二分图

• 若 $V(G)$$V(G)$ 能够划分为 $V_1,V_2$$V_1,V_2$，使得 $G$$G$ 中每条边的两个结点分别属于 $V_1,V_2$$V_1,V_2$，则称 $G$$G$ 是二分图。

• 充分必要条件：不存在奇环。

  • 证明 必要性，若不存在环，就是一棵树。

  • 如果存在环，则环上的点属于的点集应该是互相间隔的，因此不存在奇环。

  • 证明 充分性，黑白染色。设 $v_0$$v_0$ 是 $G$$G$ 中任意一点，定义 $V_1=\{v\mid v\in G,d(v,v_0)\text{为}\text{偶}\text{数}\}$$V_1=\{v \mid v \in G,d(v,v_0) 为偶数\}$，$V_2=V-V_1$$V_2=V-V_1$.

  • 若 $V_1$$V_1$ 中存在相邻节点 $v_1,v_2$$v_1,v_2$，则存在奇环 $v_0\to v_1\to v_2\to v_0$$v_0 \to v_1 \to v_2 \to v_0$，长度为奇数；$V_2$$V_2$ 亦然。

道路与回路的判定

• Warshall 算法，$u,v$$u,v$ 之间长为 $k$$k$ 的道路数目为 $A_{u,v}^k$$A_{u,v}^k$，其中 $A$$A$ 为 $G$$G$ 的邻接矩阵。所有道路总数：${\displaystyle {\left(\sum _{i=1}^{n-1}{A}^i\right)}_{u,v}}$$\displaystyle \left(\sum_{i=1}^{n-1} A^i\right)_{u,v}$. 也可以计算 ${\displaystyle (I+A{)}^n}$$\displaystyle (I+A)^n$.

  

• 搜索法、邻接矩阵法。

欧拉回路

欧拉：每条路都走一遍。

欧拉回路：连通图 $G$$G$ 中一条经过所有边的简单回路。七桥问题就是判断是否存在欧拉回路。

欧拉道路：连通图 $G$$G$ 中一条经过所有边的简单道路。

欧拉图：具有欧拉回路的图。

欧拉半图：具有欧拉道路但是无欧拉回路的图。

定理：无向 连通图 $G$$G$ 中存在欧拉回路的充要条件为 $G$$G$ 中各节点的度都是偶数。

• 必要性 每个点的进入次数和出去次数相等。

• 充分性 当 $m=1$$m=1$ 时，是自环，是欧拉图。当 $m\le k$$m \le k$ 时结论成立，证明 $m=k+1$$m=k+1$ 时结论也成立。一定存在回路 $C$$C$（蓝色），去掉回路 $C$$C$ 的部分，剩下的联通支满足每个节点都是偶数的条件，而且边数 $\le k$$\le k$，然后可以构造欧拉回路……

  

定理: 无向连通图 $G$$G$ 中存在欧拉道路(欧拉半图)的充要条件是 $G$$G$ 中只有两个度为奇数的结点。

证明: 连接这两顶点，则有回路；再删去这条边。

定理：有向连通图 $G$$G$ 中存在欧拉回路的充要条件为 $G$$G$ 中节点的入度和出度相等。

定理：有向连通图 $G$$G$ 是 欧拉半图 的充要条件为至多有两个顶点，其中一个出度比入度大一，一个入度比出度大一。

定理：设连通图 $G=(V,E)$$G=(V,E)$ 中有 $2k$$2k$ 个度数为奇数的节点，那么 $E(G)$$E(G)$ 可以划分为 $k$$k$ 条简单道路。$k$$k$ 笔画。

证明：增加 $k$$k$ 条边，连接度数为奇数的节点，形成的图各个节点的度数都为偶数，在欧拉回路上增加的边一定不相邻，否则开始节点度数应该为偶数，然后在欧拉回路上去掉新增的边，即可划分为 $k$$k$ 条简单道路。

哈密顿道路

哈密顿：每个顶点走一遍。

哈密顿 (H) 回路（道路）：无向图 $G$$G$ 的一条经过全部节点的初级回路（道路）。

• 要求 $V(G)\ge 3$$V(G) \ge 3$.

• 只需考虑简单图，因为重边和自环不起作用。

哈密顿图：具有 H 回路的图。$K_n$$K_n$ 是哈密尔顿图？需要 $n\ge 3$$n \ge 3$.

哈密顿半图：具有 H 道路而无 H 回路的图。

$H$$H$ 回路的判定很困难，没有发现充分必要条件，只有若干充分条件：

• $d(v_i)+d(v_j)\ge n$$d(v_i)+d(v_j) \ge n$，则存在 H 回路。

• 若简单图有 $H$$H$ 回路当且仅当 $C(G)$$C(G)$ 有 H 回路。

• 

引理： 设 $P:v_1,v_2,\cdots ,v_l$$P:v_1,v_2,\cdots,v_l$ 是简单图 $G$$G$ 中一条极长的初级道路，而且对于任意 $v_i,v_j$$v_i,v_j$，$d(v_i)+d(v_j)\ge l$$d(v_i)+d(v_j) \ge l$，则 $G$$G$ 中一定存在经过节点 $v_1,v_2,\cdots ,v_l$$v_1,v_2,\cdots,v_l$ 的 初级回路。

定理：若简单图 $G$$G$ 的任意两节点 $v_i$$v_i$ 与 $v_j$$v_j$ 之间恒有 $d(v_i)+d(v_j)\ge n-1$$d(v_i)+d(v_j) \ge n-1$，则存在 $H$$H$ 道路。

首先，$G$$G$ 是连通图，假设有 2 个联通支，即是每个联通支是完全图，

因此矛盾。

其次，我们构造 $H$$H$ 道路，假设 $P=v_1{v}_2\cdots v_l$$P=v_1v_2 \cdots v_l$ 是 $G$$G$ 中一条极大路径，$l\le n$$l\le n$。

• 若 $l=n$$l=n$，则 $P$$P$ 即是 $H$$H$ 道路。

• 若 $l<n$$l<n$，则 $d(v_1)+d(v_l)\ge n-1\ge l$$d(v_1)+d(v_l) \ge n-1 \ge l$，因此 $G$$G$ 中存在过 $P$$P$ 上所有点的初级回路，取 $P$$P$ 外一点 $v_{l+1}$$v_{l+1}$，如图，即可构造更长的道路：

  

重复以上步骤，即可得到 $H$$H$ 道路。

推论：若简单图 $G(n\ge 3)$$G(n \ge 3)$ 的任意两节点 $v_i$$v_i$ 和 $v_j$$v_j$ 都满足：

则存在 $H$$H$ 回路。

一定存在哈密顿道路 $P$$P$.

• 若 $v_1,v_n$$v_1,v_n$ 相邻，连接 $P$$P$ 首尾，则产生了 $H$$H$ 回路。

• 若 $v_1,v_n$$v_1,v_n$ 不相邻，定存在 $v_{i_r-1}$$v_{i_r-1}$ 在 $v_{i_r}$$v_{i_r}$ 之前，构造回路如下：

  

设 $G$$G$ 是 $n\ge 3$$n \ge 3$ 的简单图，证明：若 $m\ge \frac{1}{2}(n-1)(n-2)+2$$m \ge \frac{1}{2} (n-1)(n-2)+2$，则 $G$$G$ 存在 $H$$H$ 回路。

若任意 $v_i,v_j$$v_i,v_j$，都满足 $d(v_i)+d(v_j)\ge n$$d(v_i)+d(v_j) \ge n$，则由之前推论直到一定存在 $H$$H$ 回路。

推论：若简单图 $G(n\ge 3)$$G(n \ge 3)$ 的任何一个节点的度数都大于等于 $n/2$$n/2$，则存在 $H$$H$ 回路。

推论：若简单图 $G(n\ge 3)$$G(n \ge 3)$ 有不相邻节点 $v_i$$v_i$ 与 $v_j$$v_j$ 满足

则 $G$$G$ 中存在 $H$$H$ 回路当且仅当 $G+(v_i,v_j)$$G+(v_i,v_j)$ 有 $H$$H$ 回路。

• 若 $G$$G$ 中存在 $H$$H$ 回路则 $G+(v_i,v_j)$$G+(v_i,v_j)$ 有 $H$$H$ 回路。

• 若 $G+(v_i,v_j)$$G+(v_i,v_j)$ 有 $H$$H$ 回路则 $G$$G$ 中存在 $H$$H$ 回路，从反面证明，若 $G$$G$ 无 $H$$H$ 回路，则 $G+(v_i,v_j)$$G+(v_i,v_j)$ 无 $H$$H$ 回路。

  这种情况下，如果 $G+(v_i,v_j)$$G+(v_i,v_j)$ 存在 $H$$H$ 回路，则必然经过 $(v_i,v_j)$$(v_i,v_j)$，删除 $(v_i,v_j)$$(v_i,v_j)$，得到 $G$$G$ 中存在 $H$$H$ 道路，无初级回路，因此 $d(v_1)+d(v_l)\le n-1<n$$d(v_1)+d(v_l) \le n-1 <n$，矛盾，得证。

闭合图 若 $v_i$$v_i$ 和 $v_j$$v_j$ 是简单图 $G$$G$ 的不相邻节点，且满足 $d(v_i)+d(v_j)\ge n$$d(v_i)+d(v_j) \ge n$，则令 $G^{\prime }=G+(v_i,v_j)$$G'=G+(v_i,v_j)$，对 $G^{\prime }$$G'$ 重复以上过程，直到不再有这样的节点对为止，最终得到的图称为 $G$$G$ 的闭合图。

简单表示为，在 $C_2(G)$$C_2(G)$ 构造时没发现 $(u,v)$$(u,v)$ 的节点对。

• 若简单图有 $H$$H$ 回路当且仅当 $C(G)$$C(G)$ 有 H 回路。主要运用之前的推论。

• 若 $C(G)=K_n$$C(G)=K_n$，则 $G$$G$ 有 $H$$H$ 回路。（$C(G)$$C(G)$ 不可能做到任意两个节点度数和 $\ge n$$\ge n$ 而不是完全图）

设 $G$$G$ 是哈密顿图，则对于任意的非空 $V_1\subset V(G)$$V_1 \subset V(G)$，图 $G-V_1$$G-V_1$ 中的连通支数不大于 $|V_1|$$|V_1|$。

考虑 $G$$G$ 中的任意一条哈密顿回路 $C$$C$，$C-V_1$$C-V_1$ 的连通支数不大于 $|V_1|$$|V_1|$，而因为 $C$$C$ 是 $G$$G$ 的生成子图，所以 $C-V_1$$C-V_1$ 的连通支数又不大于 $G-V_1$$G-V_1$ 的连通支数。

不能用作判断哈密顿图的条件

但是，可以证明不是哈密顿图：

有割点的连通图不是哈密顿图。

tips: 选择的点集贪心地考虑的话，要考虑度数大的，其次考虑和之前选的点尽量不相邻的。

但是，对于 Peterson 图，都满足这个条件，但是也不是哈密顿图。

奇数个结点构成的二分图不是哈密顿图。

证:否则 H 圈是奇圈,而二部图无奇圈.

树

定义

• 树 是不含回路的连通图

  • 树必不含多重边和自环, 故是简单图

  • 边称为树枝

  • 度为1的结点称为树叶(leaf )或悬挂点

  • 度大于等于2的结点称为分叉点

• 林 是含回路的图

  • 林可能不是连通的

  • 林的每个连通支都是树-

割边 若 $G^{\prime }=G-e$$G'=G-e$ 比 $G$$G$ 的连通支数多, 则称 $e$$e$ 是 $G$$G$ 的割边.

$e=(u,v)$$e = (u,v)$ 是割边当且仅当 $e$$e$ 不属于任何回路 $\Rightarrow$$\Rightarrow$ 树中的边都是割边

树的等价定义

设 $T$$T$ 是节点数 $n\ge 2$$n \ge 2$ 的树，则下列性质互相等价：

1. $T$$T$ 连通且无回路。

2. $T$$T$ 连通且每条边都是割边。

3. $T$$T$ 连通且有 $n-1$$n-1$ 条边。

4. $T$$T$ 有 $n-1$$n-1$ 条边且无回路。

5. $T$$T$ 的任意两节点之间有唯一道路。

6. $T$$T$ 无回路，但是在任意两节点间加上一条边之后恰好有一个回路。

树是边数最少的连通图，也是边数最多的无回路图。

满足联通、无回路，$n-1$$n-1$ 条边中任意两个条件的图是树。

• 设树 $T$$T$ 的节点数 $n\ge 2$$n \ge 2$，则 $T$$T$ 中必然有树叶。

  • 考虑节点度数。

  • 考虑从任意节点 $v$$v$ 出发沿边前进，走过的边不重复，则必然止步于某树叶。

• 设树 $T$$T$ 的节点数 $n\ge 2$$n \ge 2$，则 $T$$T$ 中至少有两个树叶（从一个树叶出发）

• 若林 $F$$F$ 中有 $n$$n$ 个节点和 $k$$k$ 个连通支，则 $F$$F$ 有 $n-k$$n-k$ 条边。

生成树 定义: 如果 $T$$T$ 是图 $G$$G$ 的支撑子图, 而且是树, 则称 $T$$T$ 是 $G$$G$ 的支撑树或生成树。

图 $G$$G$ 有支撑树当且仅当 $G$$G$ 是连通的，若图 $G$$G$ 本身不是树, 则其支撑树不唯一。

余树 图 $G$$G$ 删掉生成树 $T$$T$ 中各边后的子图。

• 余树不一定连通，也不一定无回路。

• 余树不一定是树，更不一定是生成树。

Huffman树

二叉树

• 设 $T$$T$ 是有向树，若 $T$$T$ 中存在入度为 0 的节点 $v_0$$v_0$，其余节点入度为 $1$$1$，则称 $T$$T$ 是以 $v_0$$v_0$ 为根的外向树，或称 根树。

• 节点的出度最多为 2 的根树称为 二叉树；

• 除了树叶外，其余结点的出度都是 2，称为 完全二叉树。

• 一棵高度为 $k$$k$，并且具有 $2^k-1$$2^k-1$ 个结点的二叉树，称为 满二叉树。

• 若二叉树的深度为 $h$$h$，除了第 $h$$h$ 层以外，其它各层的节点数都达到最大个数，第 $h$$h$ 层的所有节点都连续集中在最左边，这就是 完全二叉树。

赋权二叉树

• 赋予树叶 $v_i$$v_i$ 一个正实数 $w_i$$w_i$.

• 带权路径总长度：

  $$\mathrm{WPL}=\sum _i{l}_i{w}_i$$

最优二叉树 给定树叶数目及其权值，构造 WPL 最小的二叉树，称为 Huffman 树。

Huffman 算法：给定 $n$$n$ 个带权树叶，构造最优二叉树。

1. 排序得 $w_{i1}\le w_{i2}\le \cdots \le w_{in}$$w_{i1} \le w_{i2}\le \cdots \le w_{in}$.

2. 计算 $w_i=w_{i1}+w_{i2}$$w_i=w_{i1}+w_{i2}$. 作为中间节点 $v_i$$v_i$ 的权值，$v_i$$v_i$ 左儿子是 $v_{i1}$$v_{i1}$，右儿子是 $v_{i2}$$v_{i2}$. $n-=1$$n-=1$.

3. 若 $n=1$$n=1$，则输出，否则继续按 1. 排序。

为什么是最优

假定 $w_1\le w_2\cdots \le w_n$$w_1\le w_2 \cdots \le w_n$，$l_i$$l_i$ 为 $v_i$$v_i$ 和根节点的距离，并且设 $T$$T$ 是最优树。

• ${\mathit{w}}_{\mathbf{1}}$$\boldsymbol{w_1}$ 离根最远，如果存在 $w_k>w_1$$w_k >w_1$ 而 $l_k>l_1$$l_k >l_1$，交换 $w_k$$w_k$ 和 $w_1$$w_1$，得到更优的二叉树，矛盾。

• ${\mathit{w}}_{\mathbf{1}}$$\boldsymbol{w_1}$ 必然有兄弟，否则将 $w_1$$w_1$ 赋值给树叶的父亲节点，可以得到更优的二叉树，其兄弟 $w_2$$w_2$ 是序列中次小的权值。

• 递推

  

  $n=2$$n=2$ 时，是最优树，将分支收缩的过程相反进行展开，最后得到的 $T_n^{\prime }$$T_n'$ 一定是最优二叉树。

  最优的条件：

  $$\begin{array}{c}\mathrm{WPL}(T_n)\le \mathrm{WPL}(T_n^{\prime })\\ \mathrm{WPL}(T_{n-1})\le \mathrm{WPL}(T_{n-1}^{\prime })\end{array}$$

  由于，之前那张图对 $T_n$$T_n$ 进行操作，$T_{n-1}$$T_{n-1}$ 进行复原：

  $$\begin{array}{c}\mathrm{WPL}(T_{n-1}^{\prime })\le \mathrm{WPL}(T_n)-(w_1+w_2)\\ \mathrm{WPL}(T_{n-1})\le \mathrm{WPL}(T_n^{\prime })-(w_1+w_2)\end{array}$$

  不等号放缩，可以得到：

  $$\begin{array}{c}\mathrm{WPL}(T_n)=\mathrm{WPL}(T_n^{\prime })\\ \mathrm{WPL}(T_{n-1})=\mathrm{WPL}(T_{n-1}^{\prime })\end{array}$$

  最优二叉树可能有很多种（交换左右子树），这里说明权值相等。

Huffman 编码

• 数据的最小冗余编码问题 使得编码序列的总长度最小；

• 译码的唯一性原则 任一字符的编码都不能是另一个字符的前缀。

前缀码 设 $\alpha ={\alpha }_1{\alpha }_2\cdots {\alpha }_{n-1}{\alpha }_n$$\alpha=\alpha_1\alpha_2\cdots \alpha_{n-1}\alpha_n$ 是长度为 $n$$n$ 的字符串，${\alpha }_1{\alpha }_2\cdots {\alpha }_k$$\alpha_1\alpha_2\cdots\alpha_k$ 称为 $\alpha$$\alpha$ 的长度为 $k$$k$ 的前缀，$k=1,2,\cdots ,n-1$$k=1,2,\cdots,n-1$，若非空字符串 ${\beta }_1,{\beta }_2,\cdots ,{\beta }_m$$\beta_1,\beta_2,\cdots,\beta_m$ 中任意两个互不为前缀，则称 $\{{\beta }_1,\cdots ,{\beta }_m\}$$\{\beta_1,\cdots,\beta_m\}$ 为前缀码，只出现 0,1 的前缀码称为二元前缀码。

最短树

• 求赋权连通图总长最小的支撑树；

• 两种算法：Kruskal, Prim.

Kruskal

将各边权重从小到大排序 while(最小生成树的边数<=总节点数-1) 找到最小的边权重，他连接的两边节点作为起始点 按从小到大的边权重顺序将节点加入图C中

定理：$T=(V,E^{\prime })$$T=(V,E')$ 是赋权连通图 $G=(V,E)$$G=(V,E)$ 的最短树，当且仅当对于任意余树边 $e\in E-E^{\prime }$$e \in E-E'$，$E^{\prime }+e$$E'+e$ 的回路 $C^e$$C^e$ 满足：

否则，$T\oplus (a,e)$$T \oplus (a,e)$ 得到的树 $T^{\prime }$$T'$ 比 $T$$T$ 更小。

Prim

需要先指定一个起始位置 while(最小生成树的边数<=总节点数-1) 寻找该点边权重最小的节点加入图C中 将图C看做一个整体，寻找C的所有边中权重最小的边，将所连点加入图C中

定理：假设 $V^{\prime }$$V'$ 是赋权连通图 $G=(V,E)$$G=(V,E)$ 的节点真子集，$e$$e$ 是端点分别属于 $V^{\prime }$$V'$ 和 $V-V^{\prime }$$V-V'$ 的最短边，则 $G$$G$ 中一定存在包含 $e$$e$ 的最短树。

如果两点集之间连边为 $e^{\prime }(\ne e)$$e'(\not=e)$，直接取 $T_0\oplus (e,e^{\prime })$$T_0 \oplus(e,e')$

匹配

引入：$m$$m$ 项工作分配给 $n$$n$ 个人去做，每人最多从事一项工作，每项工作最多由一人完成。

还可以在连边上做文章，比如可以限语言相通，一人领航一人驾驶等。

二分图匹配

定义匹配：令 $M$$M$ 是图 $G$$G$ 的边子集，若 $M$$M$ 中任意两条边都没有共同的顶点，则称 $M$$M$ 是 $G$$G$ 的一个 匹配。其中与 $M$$M$ 的边相关联的顶点称为饱和点，否则称为非饱和点。

最大匹配时 $|M|$$|M|$ 最大对应的匹配。

给定了 $G$$G$ 的一个匹配 $M$$M$，$G$$G$ 中属于 $M$$M$ 和不属于 $M$$M$ 的边交替出现的道路称为 交互道路，构成回路的交互道路称为 交互回路。

设 $P$$P$ 是 $G$$G$ 中关于匹配 $M$$M$ 的一条交互道路，如果 $P$$P$ 的两个端点是关于 $M$$M$ 的非饱和点（可以连出去新的边） ，则它称为 可增广道路。

定理：$M$$M$ 是 $G$$G$ 的最大匹配当且仅当 $G$$G$ 中不存在关于 $M$$M$ 的可增广道路。

$\Rightarrow$$\Rightarrow$ 使用反证法即可。

$\Leftarrow$$\Leftarrow$ 转化为：$G$$G$ 中不存在关于 $M$$M$ 的可增广道路时，$M$$M$ 是 $G$$G$ 的最大匹配。则需要证明当 $M$$M$ 不是 $G$$G$ 的最大匹配时一定存在可增广道路。分析 $G^{\prime }=M^{\prime }\oplus M$$G'=M' \oplus M$，$G^{\prime }$$G'$ 联通支中不可能出现度数大于 3 的节点，此时节点连出的边中存在两个同时属于 $M^{\prime }$$M'$ 或 $M$$M$. 因此，联通支只有三种情况：

1. 孤立顶点，当 $(v_i,v_j)\in M^{\prime }\cap M$$(v_i,v_j) \in M' \cap M$ 时会出现孤立点 $v_i$$v_i$ 和 $v_j$$v_j$，代表边相互抵消；

2. 初级回路，此时 $M$$M$ 的边和 $M^{\prime }$$M'$ 的边交替出现，也相当于出现次数相等；

3. 初级道路，$|M^{\prime }|\ne |M|$$|M'| \not= |M|$，只有可能在初级道路上两者出现次数不等，此时必定存在 $M^{\prime }$$M'$ 关于 $M$$M$ 的可增广交互道路。

注意 $x_4,x_5$$x_4,x_5$ 也算一条可增广交互道路。

完全匹配

$|M|=|X|$$|M|=|X|$，称为完全匹配，$|M|=|X|=|Y|$$|M|=|X|=|Y|$，称为完美匹配。

Hall 定理给出了判别完全匹配的条件：

证明：$X$$X$ 到 $Y$$Y$ 存在完全匹配的充要条件是对于 $X$$X$ 的任意子集 $A$$A$，恒有 $|\mathrm{\Gamma }(A)|\ge |A|$$|\Gamma(A)|\ge |A|$.

若存在 $|\mathrm{\Gamma }(A)|<|A|$$|\Gamma(A)| < |A|$，则 $A$$A$ 连出的边无法覆盖，因此，不存在完美匹配。

若不存在完全匹配，则设 $x_0$$x_0$ 没有匹配上，则 $x_0$$x_0$ 连到的节点一定被匹配了，而且不存在增广路，设增广路左边节点的集合为 $X_1$$X_1$，右边节点的集合为 $Y_1$$Y_1$，根据匹配的性质，$Y_1$$Y_1$ 的顶点与 $X_1-x_0$$X_1-x_0$ 的顶点存在一一对应，因此 $|X_1|=1+|Y_1|>|\mathrm{\Gamma }(X_1)|$$|X_1|=1+|Y_1| > |\Gamma(X_1)|$. 矛盾。

定理 在二分图 $G=(X,Y,E)$$G=(X,Y,E)$ 中，$X$$X$ 到 $Y$$Y$ 最大匹配的边数是 $|X|-\delta (G)$$|X|-\delta(G)$，其中 $\delta (G)=\underset{A\subseteq x}{max}\delta (A)$$\delta(G)=\max_{A \subseteq x} \delta(A)$，$\delta (A)=|A|-|\mathrm{\Gamma }(A)|,\delta (A)\ge 0$$\delta (A)=|A|-|\Gamma(A)|,\delta(A)\ge 0$.

二分图最大匹配的König定理

利用最小割最大流定理的证明：原点向左边连流量为 $1$$1$ 的边，然后原来的边流量为 $+\mathrm{\infty }$$+\infin$，右边向汇点连流量 $1$$1$ 的边。最大流对应最大匹配，最小割割掉的边和点对应，割掉之后，相当于断开这个点相连的所有边。

最大独立集是最小点覆盖的补集，如果补集中有两点相连，说明这条边没有在最小点覆盖中覆盖到。

网络流

jyy 的引入：求不相交路径个数

我们考虑一个这样的问题，假设图 $G$$G$ 节点可以分为 $S,T$$S,T$ 两个集合，其中 $S$$S$ 没有向 $T$$T$ 连任何一条边，若 $s\in S,t\in T$$s \in S,t \in T$，则从 $s$$s$ 到 $t$$t$ 没有路径。我们再考虑，若用 $\mathrm{Cut}(S,T)$$\operatorname{Cut}(S,T)$ 表示从 $S$$S$ 向 $T$$T$ 连的边数目，给定 $s,t$$s,t$，最小割定义为：

最小割对应的 $S,T$$S,T$ 集合称为 $S^{\ast }$$S^*$ 和 $T^{\ast }$$T^*$.

再考虑从 $s$$s$ 到 $t$$t$ 的最多边不重复路径个数 $\mathrm{MaxRoute}$$\operatorname{MaxRoute}$，可以发现对于每一条路径，由于其从 $S^{\ast }$$S^*$ 中的节点 $s$$s$ 出发，到 $T^{\ast }$$T^*$ 中的节点 $t$$t$ 结束，因此，路径中必然存在一条边，连接了 $u\in S^{\ast },v\in T^{\ast }$$u\in S^*,v \in T^*$，而最多有 $\mathrm{MinCut}$$\operatorname{MinCut}$ 这么多的这样的边，因此，可得：

再考虑怎么证明等号可以取到，这里，我们考虑朴素的贪心：看到了一条路径，就取这条路径。

• 假设我们第一次取 $1\to 2\to 4\to 6$$1\to 2 \to 4 \to 6$，那么第二次取 $1\to 3\to 4\to 5\to 6$$1\to 3\to 4\to 5\to 6$，万事大吉。

• 但是我们如果第一次取 $1\to 2\to 3\to 4\to 6$$1\to2\to3\to4\to6$，导致第二次无路可走，如何避免这种情况发生？

类似于二分图最大匹配，我们采用反悔的机制。再考虑二分图最大匹配的证明，证明里面使用了对称差，其本质是一种加法，因此可以考虑给正向边和反向边都赋予权值，然后我们求出来路径里面，正向边和反向边是可以抵消的。

一开始，我们给所有正向的边赋予权值 1，所有反向的边赋予权值 0，假设我们决定取这条边，则正向赋予 0，反向赋予 1，代表我们可以反悔，通过后来反向取这条边，来不取这条边。

举例，假设我们先取了 $1\to 2\to 3\to 4\to 6$$1\to2\to3\to4\to6$，边权如下：

容易发现存在路径 $1\to 3\to 2\to 4\to 5\to 6$$1 \to 3\to 2\to 4\to 5\to 6$，因此，继续取这条路径。

这两条路径进行抵消，可以得到 $1\to 2\to 4\to 6$$1\to 2 \to 4 \to 6$，$1\to 3\to 4\to 5\to 6$$1\to 3\to 4\to 5\to 6$。

再考虑一条新路径和原路径抵消之后为什么会多出来一条路径，这个其实和二分图增广路的思想差不多，画个图比较容易理解。

再考虑为什么算法结束的时候，一定能找到 $\mathrm{MinCut}$$\operatorname{MinCut}$ 条路径，假设算法结束时，找到了 $m$$m$ 条路径。

• 由之前的推导，$m\le \mathrm{MaxRoute}\le \mathrm{MinCut}$$m \le \operatorname{MaxRoute} \le \operatorname{MinCut}$.

• $m$$m$ 条路径对应了原图最小割，$m\ge \mathrm{MinCut}$$m\ge \operatorname{MinCut}$.

因此，$m=\mathrm{MaxRoute}=\mathrm{MinCut}$$m = \operatorname{MaxRoute} = \operatorname{MinCut}$.

利用重边，这种方法可以推广到边权为整数的情况，进而推广到非整数的情况。

最大流最小割定理

可以用这种方法理解网络流中的对偶性，即最大流=最小割，还可以用线性规划的方法理解：

假设有 $k$$k$ 种可能的路径 $p_1,\cdots ,p_k$$p_1,\cdots,p_k$，其对应的流量为 $f_1,\cdots ,f_k$$f_1,\cdots,f_k$，假设有 $m$$m$ 条边 $e_1,\cdots ,e_m$$e_1,\cdots,e_m$，由每条边流量的限制：

转化为对偶形式，假设第 $j$$j$ 个不等式取 ${\lambda }_j$$\lambda_j$ 倍，则：

这其实就对应了最小割，表示任意一条路径都不能通过。

容易发现这样的线性规划 $k$$k$ 比较大，参数量多，求解困难，但是相对容易理解。我们还可以将流过边的流量设为参数，发现源点流出的、汇点汇入的时网络的总流量，并且满足节点没有流量残余，即最大流：

可得它的对偶问题为：

对应了最小割。

E-K 算法

xxxxxxxxxx
33
1
int dfs(int c, int t, int f) {
2
    if (c == t) {
3
        return f;
4
    }
5
    used[c] = true;
6
    for (int i = 0; i < G[c].size(); ++ i) {
7
        Edge &e = G[c][i];
8
        if (!used[e.to] && e.cap > 0) {
9
            int d = dfs(e.to, t, min(f, e.cap));
10
            if (d > 0) {
11
                e.cap -= d;
12
                G[e.to][e.rev].cap += d;
13
                return d;
14
            }
15
        }
16
    }
17
    return 0;
18
}
19

20
int max_flow(int s, int t) {
21
    int flow = 0;
22
    int cnt = 0;
23
    for (;;) {
24
        memset(used, 0, sizeof(used));
25
        int f = dfs(s, t, INF);
26
        cnt += 1;
27
        if (f == 0) {
28
            cout << cnt << endl;
29
            return flow;
30
        }
31
        flow += f;
32
    }
33
}

效率低的原因，是因为一次只找一条增广路。

Dinic 算法

核心思想在于每次找多条增广路。

xxxxxxxxxx
20
1
 bool BFS() {
2
    memset(vis, 0, sizeof(vis));
3
    queue<int> Q;
4
    Q.push(s);
5
    d[s] = 0;
6
    vis[s] = 1;
7
    while (!Q.empty()) {
8
      int x = Q.front();
9
      Q.pop();
10
      for (int i = 0; i < G[x].size(); i++) {
11
        Edge& e = edges[G[x][i]];
12
        if (!vis[e.to] && e.cap > e.flow) {
13
          vis[e.to] = 1;
14
          d[e.to] = d[x] + 1;
15
          Q.push(e.to);
16
        }
17
      }
18
    }
19
    return vis[t];
20
  }

BFS 算法求出有余量的，构建分层图-

xxxxxxxxxx
15
1
 int DFS(int x, int a) {
2
    if (x == t || a == 0) return a;
3
    int flow = 0;
4
    for (int& i = cur[x]; i < G[x].size(); i++) {
5
      Edge& e = edges[G[x][i]];
6
      if (d[x] + 1 == d[e.to] && (f = DFS(e.to, min(a, e.cap - e.flow))) > 0) {
7
        e.flow += f;
8
        edges[G[x][i] ^ 1].flow -= f;
9
        flow += f;
10
        a -= f;
11
        if (a == 0) break;
12
      }
13
    }
14
    return flow;
15
  }

遍历分层图上的后继节点，只要当前可用流量能够承受，就继续分叉，这样可以一次找多条增广路。

平面图转对偶图

如果图 $G$$G$ 是一张平面图，还可以通过转为对偶图的方法，用最短路求最小割。

如图，如果源点是橙色的点，汇点是绿色的点，建立对偶图，在源-汇连线左手侧的边界边连到最短路的超级源点，右手侧的边界边连到最短路的超级汇点，最短路即对应最小割。

发现这样平面图的节点数和边数都是 $m$$m$ 量级，最短路时间复杂度 $\mathcal{O}(m\log m)$$\mathcal O(m \log m)$，而原图网络流用 Dinic 算法复杂度 $\mathcal{O}(m{n}^2)$$\mathcal O(mn^2)$，可见优化程度比较大。

最小费用最大流

每条边新增单位流量的费用 $w(e)$$w(e)$，满足斜对称性，即 $e$$e$ 反向，费用取相反数，要求在最大化最大流的情况下，最小化：

思路是每次寻找单位流量费用最小的增广路：$w$$w$ 的最短路。

xxxxxxxxxx
50
1
struct qxx {
2
  int nex, t, v, c;
3
};
4

5
qxx e[M];
6
int h[N], cnt = 1;
7

8
void add_path(int f, int t, int v, int c) {
9
  e[++cnt] = (qxx){h[f], t, v, c}, h[f] = cnt;
10
}
11

12
void add_flow(int f, int t, int v, int c) {
13
  add_path(f, t, v, c);
14
  add_path(t, f, 0, -c);
15
}
16

17
int dis[N], pre[N], incf[N];
18
bool vis[N];
19

20
bool spfa() {
21
  memset(dis, 0x3f, sizeof(dis));
22
  queue<int> q;
23
  q.push(s), dis[s] = 0, incf[s] = INF, incf[t] = 0;
24
  while (q.size()) {
25
    int u = q.front();
26
    q.pop();
27
    vis[u] = 0;
28
    for (int i = h[u]; i; i = e[i].nex) {
29
      const int &v = e[i].t, &w = e[i].v, &c = e[i].c;
30
      if (!w || dis[v] <= dis[u] + c) continue;
31
      dis[v] = dis[u] + c, incf[v] = min(w, incf[u]), pre[v] = i;
32
        // 记录 SPFA 路径
33
      if (!vis[v]) q.push(v), vis[v] = 1;
34
    }
35
  }
36
  return incf[t];
37
}
38

39
int maxflow, mincost;
40

41
void update() {
42
  maxflow += incf[t];
43
  for (int u = t; u != s; u = e[pre[u] ^ 1].t) {
44
    e[pre[u]].v -= incf[t], e[pre[u] ^ 1].v += incf[t];
45
    mincost += incf[t] * e[pre[u]].c;
46
  }
47
}
48

49
// 调用：while(spfa())update();
50