4 图论

4.1 图

有向图：设 \(V\) 是一个非空集，\(E \subseteq V^2\)，称有序对 \((V, E)\) 为有向图，记作 \(G = (V, E)\) 或 \(G(V, E)\)

无向图：设 \(V\) 是一个非空集，\(E\) 是 \(V\) 中两个元素多重集的集合，称有序对 \((V, E)\) 为无向图或图，记作 \(G = (V, E)\) 或 \(G(V, E)\)
1. 有向图中，\(E\) 称为弧集，\(E\) 中的元素称为弧；无向图中，\(E\) 称为边集，\(E\) 中的元素称为边
  1. 自环：若 \((a, a) \in E\)，则称该弧为自环
  2. 多重边：若图中连接两个节点之间的边不止一条，则称这些边为多重边
  3. 设 \((a, b) \in E\)，则节点 \(a, b\) 称为该弧的端点，\(a\) 为起点，\(b\) 为终点，并称 \(a, b\) 与弧 \((a, b)\) 关联
  4. 一个节点关联于几条弧，则称这些弧是弧相邻或弧邻接
2. \(V\) 称为节点集，\(V\) 中元素称为节点或点
  1. 若 \(V\) 中某节点与 \(E\) 中任何弧都不关联，则称该节点为孤立点
  2. 与一条弧相关联的两个节点称为相邻的或邻接的
3. 简单图：无自环的非多重图
  1. 零图：边集为空集的图
  2. 平凡图：只有一个节点的图
  3. 完全图 \(K_n\)：每两个节点之间恰有一条边的图，若该图的节点数为 \(n\)，则该图记为 \(K_n\)
4. 带权图：设 \((V, E)\) 是一个图，\(f: V \to \mathbf R, g: E \to \mathbf R\) 是两个函数．称有序三元组 \(G = (V, E, f)\) 或 \(G = (V, E, g)\) 以及有序四元组 \(G = (V, E, f, g)\) 为带权图
邻接矩阵：设 \(G\) 是 \(n\) 个节点，无多重边的（有向）图．\(n \times n\) 矩阵 \(M = (m_{ij})\) 依节点次序 \(v_1, v_2, \cdots, v_n\) 标记在矩阵的行与列上，也记为 \(M(G)\)，其中

\[ m_{ij} = \left\{\begin{aligned} & 1, & v_i \textsf{ 与 } v_j \textsf{ 相邻或有一条弧} \\ & 0, & \textsf{否则} \end{aligned}\right. \]

称 \(M(G)\) 为 \(G\) 的邻接矩阵
1. 当 \(G\) 为无向图时，\(M^k \ (k \in \mathbf Z_+)\) 是对称矩阵
2. 设 \(M^k = (m_{ij}^{(k)}) \ (k \in \mathbf Z_+)\)，则 \(M^k\) 中 \(m_{ij}^{(k)}\) 等于节点 \(V_i\) 与 \(V_j\) 之间长度为 \(k\) 的（有向）路径数目
节点度数：设 \(G = (V, E)\) 是一个图，节点 \(v\) 所关联的边数称为节点 \(v\) 的读书，记为 \(d(v)\)，令 \(\Delta(G) = {\displaystyle \max_{v \in V} d(v)}\) 且 \(\delta(G) = {\displaystyle \min_{v \in V} d(v)}\)
1. 度数为 \(1\) 的节点称为悬挂点；度数为奇（偶）数的节点称为奇（偶）节点
2. 握手定理：设图 \(G\) 有节点 \(v_1, v_2, \cdots, v_n\) 有 \(e\) 条边，则 \({\displaystyle \sum_{i=1}^n d(v_i) = 2e}\)
3. 度数列：设图 \(G = (V， E), V = \{v_1, v_2, \cdots, v_n\}\)，称 \(\left<d(v_1), d(v_2), \cdots, d(v_n)\right>\) 为 \(G\) 的度数列
  1. 可图化：给出非负整数列 \(d = \left<d(v_1), d(v_2), \cdots, d(v_n)\right>\)，若存在以 \(V = \{v_1, v_2, \cdots, v_n\}\) 为节点集的图，以 \(d\) 为度数列，则称 \(d\) 是可图化的；如果 \(d\) 是可图化的且图为简单图，则称 \(d\) 是可简单图化的
  2. \(d = \left<d_1, d_2, \cdots, d_n\right> \ (d_i \geqslant 0, i = 1, 2, \cdots, n)\) 是可图化的当且仅当 \({\displaystyle \sum_{i=1}^n d_i}\) 为偶数
  3. 设非负整数列 \(d = \left<d_1, d_2, \cdots, d_n\right>, (n-1) \geqslant d_1 \geqslant d_2 \geqslant \cdots \geqslant d_n \geqslant 0\)，则 \(d\) 可简单图化当且仅当对于每个满足 \(1\leqslant r \leqslant n -1\) 的整数 \(r\) 都有 \({\displaystyle \sum_{i=1}^r d_i \leqslant r(r-1) + \sum_{i=r+1}^n \min\{r, d_i\}}\) 且 \({\displaystyle \sum_{i=1}^n d_i}\) 为偶数
  4. 设非负整数列 \(d = \left<d_1, d_2, \cdots, d_n\right>\)，\({\displaystyle \sum_{i=1}^n d_i}\) 为偶数且 \((n-1) \geqslant d_1 \geqslant d_2 \geqslant \cdots \geqslant d_n \geqslant 0\)，则 \(d\) 可简单图化当且仅当 \(d' = \left<d_2 - 1, d_3 - 1, \cdots, d_{d_1} + 1, d_{d_1 + 2}, \cdots, d_n\right>\) 是可简单图化的
4. 入度与出度：设 \(G\) 是一个有向图，以节点 \(v\) 为起点的弧数称为 \(v\) 的出度，记作 \(d^+(v)\)；以节点 \(v\) 为终点的弧数称为 \(v\) 的入度，记作 \(d^-(v)\)．在有向图中，所有节点的入度之和等于所有节点的出度之和
图同构
1. 无向图的同构：设 \(G_1 = (V_1, E_1), G_2 = (V_2, E_2)\) 是两个图，如果存在两个双射 \(f: V_1 \to V_2, g: E_1 \to E_2\) 使得 \(G_1\) 中的边 \(e\) 与节点 \(v, w\) 相关联当且仅当 \(G_2\) 中的边 \(g(e)\) 与节点 \(f(v), f(w)\) 相关联，则称 \(G_1\) 与 \(G_2\) 是同构的，记作 \(G_1 \cong G_2\)，称 \(f, g\) 为 \(G_1\) 到 \(G_2\) 的同构函数
  1. 两个图同构当且仅当对某一节点的顺序，其邻接矩阵相同
  2. 设 \(G_1\) 与 \(G_2\) 是两个简单图，则 \(G_1\) 与 \(G_2\) 同构等价于如下命题：存在一个从 \(G_1\) 的节点集到 \(G_2\) 的节点集上的双射函数 \(f\)，\(G_1\) 的节点 \(v\) 与 \(w\) 相邻接当且仅当 \(G_2\) 中的节点 \(f(v)\) 与 \(f(u)\) 相邻接
2. 有向图的同构：设 \(G_1 = (V_1, E_1), G_2 = (V_2, E_2)\) 是两个有向图，若存在两个双射 \(f: V_1 \to V_2, g: E_1 \to E_2\) 使得对任何 \(u, v \in V, (u, v) \in E\) 有 \(g((u, v)) = (f(u), f(v))\)，则称 \(G_1\) 与 \(G_2\) 同构，记作 \(G_1 \cong G_2\)，称 \(f, g\) 为 \(G_1\) 到 \(G_2\) 的同构函数
子图、补图与图子式
1. 子图：设图 \(G = (V, E)\)，若在图 \(G' = (V', E')\) 有 \(V' \subseteq V, E' \subseteq E\) 且 \(E'\) 中边所关联的节点在 \(V'\) 中，则称 \(G'\) 为 \(G\) 的子图
  1. 生成子图：若 \(V' = V, E' \subseteq E\)，则子图 \(G' = (V', E')\) 称为图 \(G\) 的一个生成子图
  2. 导出子图：若 \(V' \subseteq V\)，以 \(V'\) 为节点集，端点均在 \(V'\) 中的所有边的全体为边集，构成的子图称为由 \(V'\) 导出的 \(G\) 的子图，又称为 \(G\) 的导出子图，记为 \(G(V')\)
    
    团
    
    若图 \(V\) 的一个导出子图 \(G(V')\) 是完全图，则称该图为团，定义 \(\omega(G)\) 为 \(G\) 中最大团的节点数
  3. 边导出子图：若 \(E' \subseteq E\)，以 \(E'\) 为边集，\(E'\) 中边的端点全体为节点集，构成的子图称为由 \(E'\) 导出的 \(G\) 的子图，又称为 \(G\) 的边导出子图，记为 \(G(E')\)
2. 补图：设图 \(G = (V, E)\) 是 \(n\) 个节点的任意简单图，从完全图 \(K_n\) 中删去 \(G\) 的所有边，但保留节点 \(V\) 所得到的图成为 \(G\) 的补图，记为 \(\overline G\)
3. 图子式：设 \(G, H\) 为两个图，若图 \(G\) 可通过一系列的删除边和顶点、收缩边得到图 \(H\)，则称 \(H\) 是 \(G\) 的子式或次图，也称为图 \(G\) 的 \(H-\)子式
割集：设 \(D\) 是图 \(G\) 的边集，若 \(G\) 删去 \(D\) 的全部边后所得的秩减少 \(1\)，而 \(D\) 的任何真子集均无此性质，则称 \(D\) 为 \(G\) 的割集
1. 边割：设图 \(G\) 节点非空子集为 \(V' \subseteq V\)，在 \(G\) 中的一个端点在 \(V'\) 中，另一个端点在 \(V - V'\) 中的所有边组成的集合称为 \(G\) 的一个边割或断集，记为 \(E(V' \times \overline{V'})\) 或简记为 \((V', \overline{V'})\)
  1. 当 \(|(V', \overline{V'})| = 1\) 时，\((V', \overline{V'})\) 的那条边就是割边或桥
  2. 割集是边割，反之则不一定成立
2. 点割：设图 \(G\) 的节点子集 \(V'\) 有 \(\omega(G - V') > \omega(G)\)，则称 \(V'\) 为 \(G\) 的一个点割．当 \(|V'| = 1\) 时，\(V'\) 中的节点称为割点
  1. 有割点的非平凡连通图称为可分图，没有割点的非平凡连通图称为不可分图
  2. 有割点的连通图是 \(1-\)连通的，但不是 \(2-\)连通的，反之亦然
  3. 设 \(v\) 是连通图 \(G\) 的一个节点，以下论断等价
    1. \(v\) 是 \(G\) 的一个割点
    2. 对于节点 \(v\)，存在两个不同的节点 \(u\) 和 \(w\) 使节点 \(v\) 在每一条从 \(u\) 到 \(w\) 的路上
    3. 存在 \(V - \{v\}\) 的一个分成 \(U\) 和 \(W\) 的划分，使对任意两节点 \(u \in U\) 和 \(w \in W\)，节点 \(v\) 在每一条从 \(u\) 到 \(w\) 的路上
  4. 设 \(G\) 是节点数 \(n \geqslant 3\) 的连通图，以下论断等价
    1. \(G\) 中没有割点
    2. \(G\) 的任意两个节点在同一条回路上
    3. \(G\) 的任意一个节点和任意一条边在同一条回路上
    4. \(G\) 的任意两条边在同一条回路上
独立集与覆盖集
1. 点覆盖与边覆盖
  1. 点覆盖：设无自环图 \(G = (V, E)\)，若 \(V\) 的一个子集 \(C\) 中每一条边至少有一个端点在 \(C\) 中，则称 \(C\) 是 \(G\) 的一个点覆盖，若 \(G\) 中无满足 \(|C'| < |C|\) 的点覆盖，则称 \(C\) 是 \(G\) 的最小点覆盖，其顶点数称为 \(G\) 的点覆盖数，记为 \(\alpha_0(G)\)
  2. 边覆盖：设无自环图 \(G = (V, E)\)，若 \(E\) 的一个子集 \(L\) 使得 \(G\) 的每一个顶点至少与 \(L\) 中一条边关联，则称 \(L\) 是 \(G\) 的一个边覆盖．若 \(G\) 中无满足 \(|L'| < |L|\) 的边覆盖 \(L'\)，则称 \(L\) 是 \(G\) 的最小边覆盖，其边数称为 \(G\) 的边覆盖数，记为 \(\alpha_1(G)\)
2. 独立集：设无自环图 \(G = (V, E)\)，若 \(V\) 的一个子集 \(I\) 中任意两个顶点在 \(G\) 中都不相邻，则称 \(I\) 是 \(G\) 的一个独立集．若 \(G\) 中无满足 \(|I'| > |I|\) 的独立集 \(I'\)，则称 \(I\) 为 \(G\) 的最大独立集，其顶点数称为 \(G\) 的独立数，记作 \(\beta_0(G)\)
  1. \(\text{Hall}\) 定理：对于二分图 \(G(V_1, V_2)\)，存在一匹配 \(M\) 使得 \(V_1\) 的所有顶点关于 \(M\) 饱和的充要条件是对 \(V_1\) 的任一子集 \(A\)，和 \(A\) 邻接的点集为 \(p[A]\) 恒有 \(|p[A]| \geqslant |A|\)
  2. 边独立集：设无自环图 \(G = (V, E)\)，若 \(E\) 的一个子集 \(M\) 中的任意两条边都没有公共点，则称 \(M\) 是 \(G\) 的一个边独立集，也称作 \(G\) 的一个匹配．若 \(G\) 中无满足 \(|M'| > |M|\) 的边独立集 \(M'\)，则称 \(I\) 为 \(G\) 的最大独立集，其边数称为 \(G\) 的边独立数，记作 \(\beta_1(G)\)
3. \(\text{K}\ddot{\mathrm o}\text{nig}\) 定理：在二分图 \(G(V_1, V_2)\) 中有 \(\beta_1(G) = \alpha_0(G)\)，若 \(\delta(G) > 0\)，则 \(\beta_0(G) = \alpha_1(G)\)
  1. 对于 \(n\) 个顶点的图 \(G\)，有 \(\alpha_0(G) + \beta_0(G) = n\)，若 \(\delta(G) > 0\)，则有 \(\alpha_1(G) + \beta_1(G) = n\)
  2. 设 \(G = (V, E)\) 是一个图，则 \(V\) 的子集 \(I\) 是 \(G\) 的独立集当且仅当 \(V - I\) 是 \(G\) 的点覆盖
  3. 设 \(M\) 是一个边独立集，\(C\) 是点覆盖且 \(|M| = |C|\)，则 \(M\) 是最大匹配，\(C\) 是最小点覆盖

4.1.1 连通度

路与回路：对于图 \(G = (V, E)\) 的一个有限点边交替序列 \(r = \left<v_0, e_1, v_1, e_2, \cdots, e_m, v_m\right>\)
1. 路径：若 \(r\) 对 \(1 \leqslant i \leqslant m\) 有 \(e_i\) 的端点是 \(v_{i-1}\) 与 \(v_i\)，则称序列 \(r\) 为一条路径；当 \(v_0 = v_m\) 时，称序列 \(r\) 为闭路径
2. 链：边 \(e_1, e_2, \cdots, e_m\) 互不相同的路径，其长度为 \(m\)；当 \(v_0 = v_m\) 时，称序列 \(r\) 为闭链
3. 路：节点 \(v_0, v_1, \cdots, v_m\) 互不相同的链
  1. 回路：节点 \(v_1, v_2, \cdots, v_m\) 互不相同的闭链称为回路，并根据其长度分为奇（偶）回路
  2. 距离：在 \(G = (V, E, \omega)\) 中，路 \(p\) 上的所有边带的权之和称为路 \(p\) 的长度，记为 \(\omega(p)\)．节点 \(u, v\) 之间的最短路长度称为 \(u, v\) 之间的距离，记为 \(d(u, v)\)
  3. 若图 \(G\) 的每个节点度数至少为 \(2\)，则 \(G\) 包含一条回路
以上概念均可定义有向图的对应概念
连通：设 \(u, v\) 是图 \(G\) 的两个不同节点，若 \(u, v\) 之间存在一条路，则称节点 \(u, v\) 是连通的
1. 连通图：若图 \(G\) 中任何两个不同节点之间存在一条路，则称 \(G\) 为连通图，否则称 \(G\) 为不连通图
  1. 连通分支：在节点集上定义等价关系 \(R\)，即对于 \(u, v \in V\) 由 \(uRv\) 当且仅当 \(u\) 和 \(v\) 连通，则 \(R\) 确定了 \(V\) 的一个划分 \(V_1, V_2, \cdots, V_m\)．每个节点子集 \(V_i\) 的导出子图 \(G_i\) 成为 \(G\) 的一个连通分支，简称分支
  2. 秩与零度：设图 \(G\) 有 \(n\) 个节点，\(e\) 条边与 \(\omega\) 个分支，称 \(n - \omega\) 为图的秩，\(e - n + \omega\) 为图的零度
2. 路径矩阵：设 \(G\) 是 \(n\) 个节点，无多重边的图，\(n \times n\) 矩阵 \(P = (p_{ij})\) 依节点次序 \(v_1, v_2, \cdots, v_n\) 标记在
可达：设 \(u, v\) 是有向图 \(G\) 的两个节点，若从 \(u\) 到 \(v\) 存在一条有向路，则称节点 \(v\) 是从 \(u\) 可达的，或称从 \(u\) 可达 \(v\)
1. 强连通图：任何两个节点是互相可达的有向图．在节点集上定义等价关系 \(R\)，即对于 \(u, v \in V\) 由 \(uRv\) 当且仅当 \(u\) 和 \(v\) 互相可达，则 \(R\) 确定了 \(V\) 的一个划分 \(V_1, V_2, \cdots, V_m\)．每个节点子集 \(V_i\) 的导出子图 \(G_i\) 成为 \(G\) 的一个强连通分支
2. 单向连通图：任何两个节点至少有一个节点从另一个节点可达的有向图，此时任何强连通图都是单向连通的
3. 弱连通图：弧的方向不考虑，任何两个节点之间存在一条路的有向图，此时任何单向连通图都是弱连通的
路径矩阵：设 \(G\) 是 \(n\) 个节点且无多重边的（有向）图，\(n \times n\) 矩阵 \(P = (p_{ij})\) 依定点次序 \(v_1, v_2, \cdots, v_n\) 标记在矩阵的行列上，也记为 \(P(G)\)，其中

\[ P_{ij} = \left\{\begin{aligned} & 1 & v_i \textsf{ 与 } v_j \textsf{ 之间至少存在一条（有向）路径} \\ & 0 & \textsf{否则} \end{aligned}\right. \]

称 \(P(G)\) 为 \(G\) 的路径矩阵
1. \(G\) 是（强）连通图当且仅当 \(P(G)\) 中元素全为 \(1\)
2. 对 \(n\) 个节点的 \(G\)，若从 \(v_i\) 到 \(v_j\) 之间存在一条路径，则从 \(v_i\) 到 \(v_j\) 必有一条长度不超过 \(n - 1\) 的路径；若 \(G\) 中存在一条闭路径，则必然存在一条长度不超过 \(n\) 的闭路径
点连通度与边连通度：对于任何一个图 \(G\) 有 \(k(G) \leqslant \lambda(G) \leqslant \delta(G)\)
1. 点连通度：设 \(G\) 是一个图，将产生一个不连通图或平凡图需要从 \(G\) 中删去的最少节点数称为 \(G\) 的点连通度，记作 \(k(G)\)，简称为 \(G\) 的连通度
  1. 若图 \(G\) 的 \(k(G) \geqslant k\)，则称 \(G\) 是 \(k-\)连通的
  2. 当 \(G\) 是不连通图或平凡图时，\(k(G) = 0\)，\(G\) 是完全图 \(K_n\) 时，\(k(K_n) = n - 1\)
  3. 连通图 \(G\) 有割点时，\(k(G) = 1\)
2. 边连通度：设 \(G\) 是一个图，将产生一个不连通图或平凡图需要从 \(G\) 中删去的最少边数称为 \(G\) 的点连通度，记作 \(\lambda(G)\)
  1. 若图 \(G\) 的 \(\lambda(G) \geqslant k\)，则称 \(G\) 是 \(k-\)边连通的
  2. 当 \(G\) 是不连通图或平凡图时，\(\lambda(G) = 0\)，\(G\) 是完全图 \(K_n\) 时，\(\lambda(K_n) = n - 1\)
  3. 连通图 \(G\) 有割边时，\(-\lambda(G) = 1\)
3. 双连通分支：在 \(G\) 的边集上建立关系，对于 \(E\) 中任意两边 \(e_1\) 与 \(e_2\)，两条边有关系当且仅当 \(e_1 = e_2\) 或 \(e_1\) 与 \(e_2\) 在一条回路上．该等价关系将边划分为等价类 \(E_1, E_2, \cdots, E_k\)，使得两条不同的边在同一类中当且仅当这两条边在同一回路上．由 \(E_i\) 导出的子图记为 \(G_i \ (1 \leqslant i \leqslant k)\)，每个子图 \(G_i\) 称为 \(G\) 的一个块，称为双连通分支

4.1.2 图着色

点着色：设 \(G\) 是一个无自环的图，对 \(G\) 的每个节点着色，使得没有两个相邻的节点着上相同的颜色，这种着色称为图的正常着色．图 \(G\) 的节点可用 \(k\) 中颜色正常着色，则称 \(G\) 为 \(k-\)可着色的，使 \(G\) 是 \(k-\)可着色的最小 \(k\) 称为 \(G\) 的色数，记为 \(\chi(G)\)，并称 \(G\) 是 \(\chi(G)\) 色的
1. 特定图的色数
  1. \(G\) 是零图当且仅当 \(\chi(G) = 1\)
  2. 对于完全图 \(K_n\) 有 \(\chi(K_n) = n\) 且 \(\chi(\overline{K_n}) = 1\)
  3. 对于 \(n\) 个节点构成的回路 \(G\)，当 \(n\) 是偶数时 \(\chi(G_n) = 2\)；当 \(n\) 是奇数时 \(\chi(G_n) = 3\)
  4. \(G\) 是二分图当且仅当 \(\chi(G) = 2\)
2. 如果图 \(G\) 节点的最大度数为 \(\Delta(G)\)，则 \(\chi(G) \leqslant 1 + \Delta(G)\)
3. \(\text{Brooks}\) 定理：如果连通图 \(G\) 的节点最大度数为 \(\Delta(G)\)，\(G\) 不是奇回路，又不是完全图，则 \(\chi(G) \leqslant \Delta(G)\)
边着色：设 \(G\) 是无自环的图，若对 \(G\) 的边着色，使得没有两条相邻的边着相同颜色，称这种着色为正常边着色．\(G\) 可用 \(k\) 中颜色正常边着色，则称 \(G\) 是 \(k-\)边可着色的．使 \(G\) 的 \(k-\)边可着色的最小 \(k\) 称为 \(G\) 的边色数，记为 \(x'(G)\)，称 \(G\) 是 \(x'(G)\) 边色的
1. \(\text{Vizing}\) 定理：设 \(G\) 是一个简单图，其节点最大度数是 \(\Delta(G)\)，则 \(x'(G) = \Delta(G)\) 或者 \(x'(G) = \Delta(G) + 1\)
2. 如果 \(G\) 是二分图，则 \(x'(G) = \Delta(G)\)
3. 设 \(K_n\) 是完全图，当 \(n\) 为奇数且 \(n \neq 1\) 时，\(x'(K_n) = n\)；当 \(n\) 为偶数时，\(x'(K_n) = n - 1\)
平面图着色：设 \(G\) 是地图，对 \(G\) 的每个面着色，使得没有两个相邻的面着上相同的颜色，这种着色称为地图的正常面着色．地图 \(G\) 可用 \(k\) 中颜色正常面着色，则称 \(G\) 是 \(k-\)面可着色的．使 \(G\) 的 \(k-\)面可着色的最小 \(k\) 称为 \(G\) 的面色数，记为 \(x^*(G)\)，并称 \(G\) 是 \(x^*(G)\) 面色的
1. 桥与地图
  1. 桥：如果图 \(G\) 的边 \(e\) 满足 \(\omega(G - e) > \omega(G)\)，则称 \(e\) 为 \(G\) 的桥或割边
  2. 地图：没有桥的连通平面图
2. 设 \(G\) 是没有自环的平面图，\(G^*\) 是 \(G\) 的对偶，则 \(G\) 是 \(k-\)可着色当且仅当 \(G^*\) 是 \(k-\)面可着色的
3. 四色定理：任何平面图 \(G\) 都是 \(4-\)可着色的
4. 二色定理：地图 \(G\) 是 \(2-\)面可着色的当且仅当它是一个 \(\text{Euler}\) 图

4.1.3 网络与流

网络：设连通无自环的带权有向图中有两个不同顶点 \(s, t\)，且在弧集 \(E\) 上定义非负整数值函数 \(C = \{c_{ij}\}\)，称该有向图为网络，记为 \(N(V, E, C)\)．称 \(s\) 为发点，\(t\) 为收点，除了 \(s\) 与 \(t\) 之外的其他顶点称为中间点．\(C\) 称为容量函数，弧 \((i, j)\) 上的容量为 \(c_{ij}\)
1. 流量：在网络 \(N(V, E, C)\) 的弧集 \(E\) 上定义一个非负整数值函数 \(f = \{f_{ij}\}\)，称 \(f\) 为网络 \(N\) 上的流，\(f_{ij}\) 称为弧 \((i, j)\) 上的流量．若无弧 \((i, j)\)，则 \(f_{ij} = 0\)，设流 \(f\) 满足以下条件
  1. 容量限制条件：对每一条弧 \((i, j)\) 由 \(f_{ij} \leqslant c_{ij}\)
  2. 平衡条件：除 \(s, t\) 照顾外的每个中间点 \(k\) 有 \({\displaystyle \sum_{i \in V} f_{ki} = \sum_{j \in V} f_{jk}}\) 且对于 \(s, t\) 有
  \[ \sum_{i \in V} f_{ki} - \sum_{j \in V} f_{jk} = \left\{\begin{aligned} & V_f, & k = s \\ & -V_f, & k = t \end{aligned}\right. \]
  
  则称 \(f\) 为网络 \(N\) 的一个可行流，\(V_f\) 为流 \(f\) 的值，或称为 \(f\) 的流量．若 \(N\) 中无可行流 \(f'\)，使 \(V_{f'} > V_f\)，则称 \(f\) 为最大流
2. 饱和：若 \(f_{ij} = c_{ij}\)，则称弧 \((i, j)\) 是饱和的，若 \(f_{ij} < c_{ij}\)，则称弧 \((i, j)\) 是未饱和的
割：设 \(N(V, E, C)\) 是有一个发点 \(s\) 和一个收点 \(t\) 的网络，若 \(V\) 划分为 \(P\) 与 \(V - P\) 使 \(s \in P, t \in V - P\)，则从 \(P\) 中的点到 \(V - P\) 中的点的所有弧集称为分离 \(s\) 与 \(t\) 的割，记作 \((P, V - P)\)
1. 割 \((P, V - P)\) 的容量使其每条弧的容量之和，记为 \(C(P, V - P) = {\displaystyle \sum_{i \in P, j \in V - P} c_{ij}}\)．若 \(N\) 中不存在割 \((P', V - P')\) 使 \(C(P', V - P') < C(P, V - P)\)，则称 \((P, V - P)\) 为最小割
2. 对于给定的网络 \(N = (V, E, C)\)，设 \(f\) 是任一个可行流，\((P, V - P)\) 是任一割，则 \(V_f \leqslant C(P, V - P)\)
3. 最大流最小割定理：在任一网络 \(N\) 中，从发点 \(s\) 到收点 \(t\) 的最大流的值等于分离 \(s\) 与 \(t\) 的最小割容量

4.1.4 图的实例

二分图：若图 \(G\) 的节点集 \(V\) 能划分为两个子集 \(V_1\) 与 \(V_2\)，且每条边的一个端点在 \(V_1\) 中，另一个端点在 \(V_2\) 中，则称 \(G\) 为二分图，记为 \(G(V_1, V_2)\)
1. 完全二分图：若简单图 \(G\) 具有划分 \(\{V_1, V_2\}\) 且 \(V_1\) 中每个节点与 \(V_2\) 中每个节点恰有一条边相连，则称 \(G\) 为完全二分图．若 \(|V_1| = m, |V_2| = n\)，这样的完全二分图记为 \(K_{m, n}\)
2. \(G\) 是二分图当且仅当 \(G\) 中没有奇回路
\(\text{Euler}\) 图：若（有向）图 \(G\) 中具有一条包含 \(G\) 中所有边的（有向）闭链，则称之为 \(\text{Euler}\)（有向）闭链，此时称 \(G\) 为 \(\text{Euler}\)（有向）图；若图 \(G\) 中具有一条包含 \(G\) 中所有边的（有向）开链，则称之为 \(\text{Euler}\)（有向）开链，此时称 \(G\) 为半 \(\text{Euler}\)（有向）图
1. 设 \(G\) 是连通图，则 \(G\) 是 \(\text{Euler}\) 图当且仅当 \(G\) 的所有节点都是偶节点；\(G\) 是半 \(\text{Euler}\) 图当且仅当 \(G\) 中有且仅有两个奇节点
2. 设 \(G\) 是连通有向图，则 \(G\) 是 \(\text{Euler}\) 有向图当且仅当 \(G\) 的每个节点 \(v\) 都满足 \(d^+(v) = d^-(v)\)；\(G\) 是半 \(\text{Euler}\) 有向图当且仅当 \(G\) 中有且仅有两个奇节点，其中一个奇节点的入度比出度大 \(1\)，另一个奇节点的出度比入度大 \(1\)；其余节点的出度等于入度
3. 一笔画问题：如果在一个图中奇节点个数为 \(2k\) 个，则该图是 \(k\) 笔画的
\(\text{Hamilton}\) 图：若（有向）图 \(G\) 具有一条包含 \(G\) 中所有节点的（有向）回路，则称该回路为 \(\text{Hamilton}\) 回路，称 \(G\) 为 \(\text{Hamilton}\)（有向）图；若图 \(G\) 具有一条包含 \(G\) 中所有节点的路，则称该回路为 \(\text{Hamilton}\) 路，此时称 \(G\) 为半 \(\text{Hamilton}\)（有向）图
1. 充分条件：若 \(G\) 是 \(n \ (n \geqslant 3)\) 个节点的简单图，对于每一对不相邻的节点 \(u, v\) 都有 \(d(u) + d(v) \geqslant n\)，则 \(G\) 是 \(\text{Hamilton}\) 图
  1. 设 \(G\) 是 \(n \ (n \geqslant 3)\) 个节点的简单图，若对于每一个节点 \(v\) 都有 \(d(v) \geqslant \dfrac{n}{2}\)，则 \(G\) 是 \(\text{Hamilton}\) 图
  2. 若 \(G\) 是 \(n\) 个节点的简单图，对于每一对不相邻的节点 \(u, v\) 都有 \(d(u) + d(v) \geqslant n - 1\)，则 \(G\) 是半 \(\text{Hamilton}\) 图
2. 必要条件：若图 \(G\) 是 \(\text{Hamilton}\) 图，则对于节点集 \(V\) 的每一个非空真子集 \(S\)，\(\omega(G - S) \leqslant |S|\) 均成立，其中 \(|S|\) 表示 \(S\) 的节点数，\(G - S\) 表示 \(G\) 中删去节点子集 \(S\) 后得到的图
3. 竞赛图：每两个节点之间恰有一条弧的有向图
  1. 任何一个竞赛图是半 \(\text{Hamilton}\) 有向图
  2. 任何一个强连通的竞赛图 \(G\) 必是 \(\text{Hamilton}\) 有向图
  3. \(\text{King} - \text{Chicken}\) 定理：在任何竞赛图中，存在最大出度节点到其他任何节点的、长度不超过 \(2\) 的有向路
平面图：若一个图能画在平面上使其边除了在节点处之外互不相交，则称该图为平面图，或称该图为能嵌入平面的
1. 面：平面图 \(G\) 嵌入平面后得到图 \(\overline G\)，将其分成若干个连通闭区域，每个连通闭区域称为 \(G\) 的一个面，其中恰有一个无界的面，称为外部面，其余的面称为内部面
2. \(\text{Euler}\) 公式：若连通平面图 \(G\) 有 \(n\) 个节点，\(e\) 条边与 \(f\) 个面，则有 \(n - e + f = 2\)
  1. 完全图 \(K_5\) 与二分图 \(K_{3, 3}\) 是非平面图
  2. 在平面简单图 \(G\) 中至少存在一个节点 \(v_0\)，有 \(d(v_0) \leqslant 5\)
3. \(\text{Kuratowski}\) 定理：图 \(G\) 是平面图当且仅当其任何子图都不是 \(K_5\) 或 \(K_{3, 3}\) 的剖分
  
  剖分
  
  设 \(G\) 是一个给定的图，对 \(G\) 实行有限次「删去一条边 \(\{u, v\}\) 后添加一个新节点 \(w\) 以及新边 \(\{u, w\}\) 与 \(\{v, w\}\)」的过程称为 \(G\) 的一个剖分
4. 几何对偶：设 \(\overline G\) 是平面图 \(G\) 的平面嵌入，则构造 \(G^*\)
  1. 在 \(\overline G\) 的每个面 \(f\) 恰放唯一的一个节点 \(f^*\)
  2. 对 \(\overline G\) 的两个面 \(f_i, f_j\) 的公共边 \(x_k\) 作边 \(x_k^* = \{f_i^*, f_j^*\}\) 与 \(x_k\) 相交
  称之为 \(G\) 的几何对偶
  1. 设 \(G\) 是有 \(n\) 个节点，\(e\) 条边与 \(f\) 个面的连通平面图，则 \(G\) 的几何对偶 \(G^*\) 有 \(f\) 个节点，\(e\) 条边与 \(n\) 个面
  2. \(G\) 是连通平面图当且仅当 \(G^{**}\) 同构于 \(G\)

4.2 树

4.2.1 基本概念

树的等价定义：设 \(T_n\) 有 \(n\) 个节点，\(e\) 条边，则以下均为树的等价定义
1. \(T\) 是连通无回路的图
2. \(T\) 是无回路图，且 \(e = n - 1\)
3. \(T\) 是连通图，且 \(e = n - 1\)
4. \(T\) 是无回路图，且在 \(T\) 的任何两个不相邻的节点之间添加一边，恰得一条回路
5. \(T\) 是最小连通图，即删去任意一边后就不连通
6. \(T\) 得每一对不同的节点之间有唯一一条路
当 \(T\) 是树时，定义如下概念
1. 叶节点与分枝节点：树中度数为 \(1\) 的节点称为叶节点，也称悬挂点或外部节点；度数大于 \(1\) 的节点称为分枝节点或内部节点
2. 森林：不相交的树全体
3. 平凡树：即平凡图
树的性质
1. 若 \(G\) 是 \(n\) 个节点，\(\omega\) 个分枝节点的森林，则 \(G\) 有 \(n - \omega\) 条边
2. 在任意一个非平凡树 \(T\) 中，至少有两个叶节点
有根树：若有一个有向树恰有一个节点的入度为 \(0\)，其余所有节点入度为 \(1\)，则称该有向树为有根树．若有根树的每个分枝节点连出的弧从左到右用正整数 \(1, 2, \cdots, i, \cdots\) 标上标号，称该有根树为有序树
1. 有向树：有向图在不考虑弧的方向时是一个树，则称该有向图为有向树
2. 层数与高：从根 \(r\) 到某一节点 \(a\) 的路径所含的边数称为 \(a\) 的层数；从根 \(r\) 到叶节点的最大层数称为树的高
3. 子树：设 \(u\) 是有根树 \(T\) 的任一节点，以 \(u\) 为根，\(u\) 及其所有后代组成的节点集 \(V^n\)，\(u\) 到这些后代的有向路上所有弧组成的弧集记为 \(E'\)，称 \(T\) 的子图 \(T'(V', E')\) 为以 \(u\) 为根的子树
4. \(m\) 分树：在树 \(T\) 中若每一节点的儿子个数小于或等于 \(m\)，则称 \(T\) 为 \(m\) 分树．在树 \(T\) 中若每一节点的儿子个数等于 \(m\) 或等于 \(0\)，称 \(m\) 为正则 \(m\) 分树．设 \(T\) 为正则二分树
  1. 若叶节点数为 \(t\)，则分枝节点数为 \(t - 1\)
  2. \(I\) 表示所有分枝节点路长度综合，\(E\) 表示所有叶节点的路长度之和，则 \(E = I + 2i\)，其中 \(i\) 为分枝节点数
当 \(T\) 是有根树时，定义如下概念
1. 叶节点与分枝节点：入度为 \(0\) 的节点是根，出度不为 \(0\) 的节点是分枝节点或内部节点，出度为 \(0\) 的节点是叶节点或外部节点
2. 父子节点与兄弟节点：若 \((a, b) \in T\)，则称 \(a\) 是 \(b\) 的父节点，\(b\) 是 \(a\) 的子节点；同一个分枝节点的子节点互为兄弟节点
3. 祖先节点与后代节点：若 \(a, b\) 是 \(T\) 的两个节点且有一条从 \(a\) 到 \(b\) 的有向路径，则称 \(a\) 是 \(b\) 的祖先节点，\(b\) 是 \(a\) 的后代节点

4.2.2 生成树

生成树：图 \(G\) 的生成子图是树 \(T\)，则称 \(T\) 为 \(G\) 的生成树．从 \(G\) 中删去 \(T\) 的边得到的图称为 \(G\) 的余树，记为 \(\overline T\)．生成树 \(T\) 中的边称为枝，余树 \(\overline T\) 中的边称为 \(G\) 的弦或连枝
1. \(G\) 是连通图当且仅当 \(G\) 有生成树
2. \(G\) 的秩是 \(G\) 的各分支中生成树的枝树之和，\(G\) 的零度是 \(G\) 的各分支中生成树的连枝树之和
3. \(\text{Cayley}\) 定理：完全图 \(K_n \ (n \geqslant 2)\) 的不同生成树总数 \(L(n) = n^{n-2}\)
割集与生成树
1. 割集与回路的性质
  1. 任何一条回路和任何生成树的余树至少有一条公共边
  2. 任何一个割集与任何生成树至少有一条公共边
  3. 任何一条回路和任何一个割集有偶数条公共边
2. 基本割集：设 \(T\) 是连通图 \(G\) 的给定生成树，对于只包含 \(T\) 中一条枝的割集，称此割集为关于 \(T\) 的基本割集
  1. 连通图 \(G\) 有 \(e\) 条边与 \(n\) 个节点，给定的生成树 \(T\) 有 \(n - 1\) 条枝，所以恰有 \(n - 1\) 个基本割集，这些割集的全体称为生成树 \(T\) 的基本割集组
  2. 在连通图中，对给定的一个生成树，设 \(D = \{e_1, e_2, \cdots, e_k\}\) 是一个基本割集，其中 \(e_1\) 是枝，\(e_2, e_3, \cdots, e_k\) 是弦，则 \(e_1\) 包含在对应于 \(e_i \ (i = 2, 3, \cdots, k)\) 的基本回路中，且 \(e_1\) 不包含在任何其他的基本回路中
3. 基本回路：设 \(T\) 是连通图 \(G\) 的给定生成树，在 \(T\) 中加一条弦，恰产生一条回路，称此回路为关于 \(T\) 的回路
  1. 连通图 \(G\) 有 \(e\) 条边与 \(n\) 个节点，给定的生成树 \(T\) 有 \(n - 1\) 条枝与 \(e - n + 1\) 条弦，所以恰有 \(e - n + 1\) 个基本回路，这些回路的全体称为生成树 \(T\) 的基本回路组
  2. 在连通图中，对给定的一个生成树，设 \(C = \{e_1, e_2, \cdots, e_k\}\) 是一条基本回路，其中 \(e_1\) 是弦，\(e_2, e_3, \cdots, e_k\) 是枝，则 \(e_1\) 包含在对应于 \(e_i \ (i = 2, 3, \cdots, k)\) 的基本割集中，且 \(e_1\) 不包含在任何其他的基本割集中
树的基本变换：设 \(T\) 是连通图 \(G\) 的生成树，在 \(T\) 的一条基本回路中删去一枝得到另一个生成树，这种变换称为树的基本变换
1. 距离：设连通图 \(G\) 的生成树 \(T_i, T_j\) 出现在 \(T_i\) 而不出现在 \(T_j\) 的变数称为 \(T_i\) 与 \(T_j\) 的距离，记作 \(d(T_i, T_j)\)
  1. \(d(T_i, T_j) = d(T_j, T_i)\)
  2. \(d(T_i, T_j) \geqslant 0\)，等号成立当且仅当 \(T_i = T_j\)
2. 设 \(T_i, T_j\) 是连通图 \(G\) 的两个不同的生成树，则由 \(T_1\) 通过有限次树的基本变换可以得到 \(T_2\)
最小生成树：设 \(G(V, E, \omega)\) 是带权连通简单图，\(\omega: E \to \mathbf R\) 是函数，\(T\) 是 \(G\) 的一个生成树．设 \(W(T) = {\displaystyle \sum_{\{i, j\} \in T} \omega(\{i, j\})}\)，则具有最小权 \(\min W(T)\) 的生成树称为最小生成树