图论与网络优化-Toy模板网

这篇具有很好参考价值的文章主要介绍了图论与网络优化。希望对大家有所帮助。如果存在错误或未考虑完全的地方，请大家不吝赐教，您也可以点击"举报违法"按钮提交疑问。

CSDN 有字数限制，因此笔记分别发布，目前：

【笔记1】概念与计算、树及其算法
【笔记2】容量网络模型、遍历性及其算法
【笔记3】独立集及其算法

2.概念与计算

2.1 图的定义

2.1.1 定义

图(graph) $G$ 是一个有序的三元组，记作 $G=<V(G),E(G),\psi (G)>$ 。
$V (G)$ 是顶点集。 $E (G)$ 是边集。 $\psi (G)$ 是关联函数。例如 $\psi_G (e)=v_iv_j$ 。
$N_G(v)$ 表示点 $v$ 的一阶邻域点。

相邻：与同一个顶点关联的两条边是相邻的。
环：两个端点重合的边称为环。
连杆：端点不重合的边成为连杆。
$k$ 重边：连接同一对顶点的 $k$ 条边。
单边：一对顶点之间只有一条边。
简单图：无环无重边。

2.1.2 度

度：与顶点 $v$ 关联的边的数目，记作 $d (v)$ 。
度序列： $d(v_1),d(v_2),...,d(v_v))$
孤立点：度为 $0$ 。
悬挂点：度为 $1$ 。
悬挂边：与悬挂点相关联的边。
偶点：度为偶数的顶点。
奇点：度为奇数的顶点。
最小度 $\delta(G)$ ：图 $G$ 顶点度的最小值。
最大度 $\Delta(G)$ ：图 $G$ 顶点度的最大值。

握手引理： $\sum_{v\in V} = 2 \varepsilon$ 。
例题：空间中不存在有奇数个面并且每个面只有奇数个棱的多面体。
思路：将面抽象为点，两面之间的棱为边，则转化成了有奇数个点且每个点都是奇数度的图，与握手引理矛盾，得证。

例题：证明非负整数序列 $d_1,d_2,...,d_v)$ 是某个图的度序列当且仅当 $\sum_{i=1}^{v} d_i$ 是偶数。
思路：先画出 $v$ 个孤立点，然后选序列中度大于 $1$ 的点连环直至将每个点仍需添加的度为 $0$ 或 $1$ 。然后将两两选择度为 $1$ 的点。能连通即可得证。

图序列：简单图的度序列。
判断是否为图序列：非负整数序列 $(d_1,d_2,...,d_v)(d_1 \geq d_2 \geq ... \geq d_v)$ 是图序列当且仅当 $\sum_{i=1}^v d_i$ 是偶数，并且对一切整数 $k(1\leq k\leq v-1$ ，有 $\sum_{i=1}^{k} \leq k(k-1) \leq \sum_{i=k+1}^{v}min \{k,d_i\}$ .
例题： $(1, 2, 2, 4, 5); (1, 2, 3, 3, 4, 5); (1, 2, 3, 4, 4, 5)$ 三个是否是图序列？
思路：第一个不是图序列，当点数为 $5$ 时，不存在度为 $5$ 的简单图。第二个是图序列。第三个不是图序列，先画出度为 $5$ 的点的连边，然后只有三个点还能连边，需要的度依次为 $2, 3, 3$ ，简单图中的三个点不可能连出度为 $3$ 的连边情况。

2.1.3 同构

同构：若两个图顶点之间建立一一对应的关系，且任意一对顶点的边数对应相同，则称两图是同构的。

2.2 子图和连通分支

2.2.1 子图

子图：设 $H$ 和 $G$ 为两个图。若 $\subseteq V(G)$ 且 $\subseteq E(G)$ ，则 $H$ 为 $G$ 的子图。记作 $\subseteq G$ 。
相等：设 $H$ 和 $G$ 为两个图。若 $V (H) = V (G)$ 且 $E (H) = E (G)$ ，则 $H$ 为 $G$ 相等。记作 $H = G$ 。
真子图：若 $\subseteq G$ 且 $\neq G$ ，则称 $H$ 是 $G$ 的真子图，记作 $\subset G$ 。
支撑(生成)子图：若 $V (H) = V (G)$ 且 $\subseteq E(G)$ ，则称 $H$ 是 $G$ 的支撑子图或生成子图。
基础简单图：对图 $G$ 去除重边和环后的图 $H$ 。

2.2.2 导出子图

导出子图：设 $V^{'}$ 是 $V (G)$ 的非空子集，以 $V^{'}$ 为顶点集，以 $\in E(G) | u,v \in V'}$ 为边集的 $G$ 的子图称为 G 的由 $V^{'}$ 导出的子图，记作 $G [V^{'}]$ ，简称为 $G$ 的导出子图。

2.2.3 连通分支

途径的起点/终点/长度/逆转/衔接/节： $W=v_oe_1v_1e_2...e_kv_k$ ，这里 $v_i\in V(0\leq i \leq k),e_j=v_{j-1}v_j \in E(1 \leq j \leq k)$ ， $v_0$ 称为 $W$ 的起点， $v_k$ 称为 $W$ 的终点，之间的 $v$ 称为 $W$ 的内部点。 $W$ 称为 $G$ 的 $v_0,v_k)$ 途径。 $k$ 为 $W$ 的长度。逆转如字面意思。衔接意味对于两个不同的 $W$ ，其中一条 $W$ 的终点为另一个 $W$ 的起点，则两条 $W$ 可以衔接。节是 $W$ 序列中的子集。

迹：途径 $w$ 的边互不相同，则称 $W$ 为迹。若起点终点相同，则 $W$ 为闭迹。
链：途径 $w$ 的顶点互不相同，则称 $W$ 为链。一个顶点也称为一条链。
圈：起点、内部点互不相同的闭迹称为圈，长为 $k$ 的圈称为 $k$ 圈。根据 $k$ 的奇偶性，相应地称 $k$ 圈为奇圈和偶圈。
连通：若图 $G$ 中存在 $(u, v)$ 链，则顶点 $u$ 和 $v$ 在图 $G$ 中是连通的。
连通分支(数)： $V$ 的非空划分 $(V_1,V_2...,V_\omega)$ ，导出子图 $G[V_1],G[V_2],...,G[V_\omega]$ 称为 $G$ 的连通分支。 $\omega(G)$ 为图 $G$ 的连通分支数。

2.2.4 距离

距离：图 $G$ 中所有 $(u, v)$ 链的最短链，记为 $d (u, v)$ ，被称之为 $u, v$ 之间的距离。
例题：设 $G$ 是连通图，且 $G$ 中至少有一对顶点不相邻，证明存在 $\in V$ ，使 $\in E$ ，但 $\notin E$ 。
思路：设 $\in V$ 且 $\notin E$ 。因 $G$ 连通，故 $G$ 中存在最短 $(x, y)$ 链 $P=xv_1v_2...y$ 。
由 $P$ 的最短性可知 $xv_2 \notin E$ ，于是令 $u=x,v=v_1,w=v_2$ ，则有 $\in E,vw \in E$ 但 $\notin E$ 。

2.3 重要图类

2.3.1 完全图

完全图：含有 $C_{n}^{2}$ 条边，且每对顶点都相邻的简单图，记作 $K_n$ 。
空图：边集为空的图。
平凡图：图中只有一个顶点。
非平凡图：除了平凡图以外的图。
例题：在任意 $6$ 个人聚会上，要么有 $3$ 个人相互认识，要么有 $3$ 个人相互不认识。
思路：先构造 $6$ 阶完全图 $K_6$ ，其中 $V = {v_1,v_2,...,v_6}$ 。 $v_i$ 代表第 $i$ 个人。
若 $v_i$ 与 $v_j$ 互相认识，则染这条边为红色边，否则为蓝色边。于是问题转成了图中必定存在同色三角形问题。因此得证。

2.3.2 正则图

正则图/k正则图：每个顶点的度都相等(都为 $k$ )的图称为( $k$ )正则图。一般指的是简单图。
例题：对于任意的正整数 $n$ , $nk$ 为偶数，当 $\geq k + 1$ ， $n$ 阶 $k$ 正则图存在吗？
思路：
$\gamma_1$ 法则：构造偶数正则图法则。
设 $G$ 是 $v$ 阶 $k$ 正则图，且 $k = 2 m$ ， $\geq 1$ ，按以下步骤生成新图 $G^{'}$ ：
step 1：在图 $G$ 中任取 $m$ 条互不相邻的边： $v_1v_2,v_3v_4,...,v_{2m-1}v_{2m}$ 并删除。
step 2：增加新的顶点 $v$ ，并向所有被删边的点增加一条新边 $vv_i(i=1,2,...,2m)$ ，得到新图 $G^{'}$ 。

$\gamma_2$ 法则：构造奇数正则图法则。
设 $G$ 是 $v$ 阶 $k$ 正则图，且 $k = 2 m + 1$ ， $\geq 1$ ，按以下步骤生成新图 $G^{'}$ ：
step 1：在图 $G$ 中任取 $m$ 条互不相邻的边： $v_1v_2,v_3v_4,...,v_{2m-1}v_{2m}$ 并删除。
step 2：再在图 $G$ 中任取 $m$ 条互不相邻的边： $u_1u_2,u_3u_4,...,u_{2m-1}u_{2m}$ 并删除。
(step 1 和 step 2 中可能会出现重复点)
step 3：增加新的顶点 $w_1$ ，并向 step 1 中所有被删边的点增加一条新边 $w_1v_i(i=1,2,...,2m)$ 。
step 4：再增加新的顶点 $w_2$ ，并向 step 2 中所有被删边的点增加一条新边 $w_2u_i(i=1,2,...,2m)$ 。
step 5：加边 $w_1w_2$ ，得新图 $G^{'}$ 。

定理： $n$ 阶 $k$ 正则简单图存在的充要条件是 $\leq n-1$ 且 $nk$ 为偶数。
证明：设 $G$ 是 $n$ 阶 $k$ 正则简单图，每个顶点最多与其他 $n - 1$ 个顶点相邻，因此 $\leq n-1$ 成立。
设 $k = 2 m$ ，取 $G=K_{k+1}$ ，则 $G$ 为 $k$ 正则图。根据 $\gamma_1$ 法则，顶点每次可以增加 $1$ 而点的度数不变。因此可以得到 $n$ 阶 $k$ 正则图。

2.3.3 二部图

(完全)二部图：若顶点集可以划分为两个子集 $X$ 和 $Y$ ，使得 $G$ 中每条边的一端点在 $X$ 中，另一个端点在 $Y$ 中，则称 $G$ 图为二部图。二部图 $G$ 记作 $G = (X, Y, E)$ 。若集合 $X$ 中的每个点都与 $Y$ 中所有点都恰好有一条边，且 $X 、 Y$ 均不为空集，则该图记作完全二部图，记作 $K_{m,n}$ 。

定理：图 $G$ 的二部图，当且仅当 $G$ 中不含奇圈。
证明：
step 1：
设 $G = (X, Y, E)$ 是二部图， $C=(v_0v_1...v_kv_0)$ 是 $G$ 中的一个圈，长度为 $k + 1$ 。
设 $v_0 \in X$ ，于是后面节点依次属于 $Y$ 和 $X$ 。因此得到 $v_{2i} \in X，v_{2i+1} \in Y$ 。
因此 $k = 2 l + 1$ 。该圈为偶圈。
step 2：
设 $G$ 连通(若不连通则取一个连通分支证明之)。在 $G$ 中任取一个顶点 $u$ ，令 $X=\{x|d(u,x)为偶数\}$ ， $Y=\{y|d(u,y)为奇数\}$ 。显然 $X 、 Y$ 是图 $G$ 的一个划分。
为了证明 $G$ 是二部图，只需证明 $X$ 或 $Y$ 中任何两个顶点都不相邻。
设 $v, w$ 是 $X$ 中任意两个顶点，令 $P$ 是 $G$ 中最短 $(u, v)$ 链，Q 是 $G$ 中最短 $(u, w)$ 链。
设 $P$ 与 $Q$ 的最后一个公共顶点是 $u_1$ 。因为 $P$ 和 $Q$ 都是最短链，因此 $P$ 的 $u,u_1)$ 节和 $Q$ 的 $u,u_1)$ 节都是最短 $u,u_1)$ 链，从而长度相等。如下图：
图论与网络优化,图论
又因 $P$ 和 $Q$ 的长度都为偶数，故 $P$ 的 $u_1,v)$ 节 $P_1$ 和 $Q$ 的 $u_1,w)$ 节 $Q_1$ 有相同奇偶性，于是 $(v, w)$ 链 $P_1^{-1}Q_1$ 的长是偶数。因此若 $v$ 与 $w$ 相邻，则 $P_1^{-1}Q_1wv$ 就是 $G$ 中的一个奇圈，与假设矛盾。

2.4 有向图

2.4.1 定义

有向图：有向图 $D$ 指一个有序三元组 $(V(D),A(D),\psi_D)$ ，其中 $\neq \varnothing$ ， $\cap A(D) = \varnothing$ 。 $V (D)$ 是顶点集。 $A (D)$ 是弧集。 $\psi_D$ 称为 $D$ 的关联函数，使得 $D$ 每条弧对应于 $D$ 的有序定点对。 $\psi_D(a)=(u,v)$ 中 $u$ 是弧 $a$ 的尾， $v$ 称为 $a$ 的头。

2.4.2 基础图

基础图：在有向图中去掉弧上箭头的图。
定向图：对图 $G$ 的每条边规定方向后的图。
相邻、连通、圈、子图 的概念和含义不变。

2.4.3 出度和入度

入弧：有向图 $D$ 中以顶点 $v$ 为头的弧。
出弧：有向图 $D$ 中以顶点 $v$ 为尾的弧。
入度：记作 $d_D^-(v)$ ，称为 $v$ 的入度。
出度：记作 $d_D^+(v)$ ，称为 $v$ 的出度。
对于任何有向图D，有： $\sum_{v \in V}d_D^-(v) = \sum_{v \in V}d_D^+(v) = \varepsilon(D)$

2.4.4 回路

有向途径： $W=v_0a_1v_1a_2...v_{k-1}a_kv_k$ ，其中交替项为顶点和弧。那么 $W$ 就是有向途径。 $v_0$ 称为 $W$ 的起点， $v_k$ 称为 $W$ 的终点。 $k$ 称为 $W$ 的长。 $W$ 称为有向 $v_0,v_k)$ 途径。
有向闭途径：起点与终点相同的有向途径。
有向迹：弧各不相同的有向途径。
有向链(路)：顶点各不相同的有向途径。

2.4.5 强连通分支

强连通： $u, v$ 是有向图 $D$ 中的两个顶点，若存在 $(u, v)$ 路和 $(v, u)$ 路使得两点可以相互到达，则称 $u$ 和 $v$ 在图 $D$ 中是强连通的。
强连通分支/强连通有向图： $V (D)$ 的非空划分 $V_1V_2...V_\omega$ 在 $D$ 中所导出的子图 $D[V_1],D[V_2],...,D[D_\omega]$ 称为 $D$ 的强连通分支。若 $D$ 中只有一个强连通分支，则 $D$ 是强连通有向图。

2.5 网络

2.5.1 无向网络和有向网络

无向(有向)网络：对图中每一条边都对应于一个实数 $w (e)$ ，我们把 $w (e)$ 称为边 $e$ 的边权，这样的图称为无向(有向)网络。
非负权/正权网络：网络中每条边的边权均为非负数/正数的网络。
最短路：在网络所有 $v_i,v_j)$ 路中，权最小的 $v_i,v_j)$ 路称为最短路。

2.6 矩阵表示

2.6.1 邻接矩阵

邻接矩阵： $A(G)=(a_{ij})$ 是一个 $\times v$ 矩阵， $a_{i,j}$ 等于第 $i$ 个顶点与第 $j$ 个顶点的边数。
性质：

$A^T(G)=A(G)$ 。
第 $i$ 个顶点的度等于 $2a_{ii} + \sum_{j \neq i}a_{ij}$ 。
邻接矩阵在顶点标号合适的情况下可以写成对角形式。

定理： $A^r(G)$ 中的第 $i$ 行第 $j$ 列的元素等于 $G$ 中第 $i$ 个顶点与第 $j$ 个顶点的长度为 $r$ 的不同途径的数目。
有向图的表示、性质、定理类比上面内容。

2.6.2 Laplace矩阵

Laplace矩阵：设 $G$ 为非空无环图， $A (G)$ 为图 $G$ 的邻接矩阵，对角矩阵 $D (G)$ 的主对角线上元素为对应顶点的度，则称 $D (G) - A (G)$ 为图 $G$ 的 Laplace 矩阵，记作 $L (G)$ 。
性质：

Laplace矩阵每行元素的和为 $0$ 。
矩阵的 $0$ 特征值重数是图的连通分支个数 $\omega$ 。

2.6.3 关联矩阵

关联矩阵： $M(G)=(m_{ij})$ 是一个 $\times \varepsilon$ 矩阵，其中若第 $i$ 个顶点与第 $j$ 条边关联，则为 $1$ ，否则为 $0$ 。
性质：

关联矩阵每行元素的和对应顶点的度。
关联矩阵每列恰好包含两个 $1$ 。

若是有向图，则第 $i$ 个顶点为第 $j$ 条弧的尾是 $1$ ，是头则为 $- 1$ 。

2.7 运算

2.7.1 删去和添加

删去：删边或删点。

设 $F$ 是 $E (G)$ 的非空子集， $G - F$ 表示从 $G$ 中删去 $F$ 中一切边后得到的图。若 $F={e}$ ，则 $G-{e}$ 记作 $G - e$ 。得到的新图必定是 $G$ 的支撑子图。
设 $S$ 是 $V (G)$ 的非空真子集，则 $G - S$ 表示从 $G$ 中删去 $S$ 的所有顶点及其 $S$ 中顶点关联的一切边后得到的图。同样 $G-{V}$ 简记为 $G - v$ 。显然 $G - S = G [V 反斜杠 S]$ 。

添加：加边或加点。

在图 $G$ 中添加一条以顶点 $u$ 和 $v$ 为端点的边 $e$ ，得到的图记为 $G + e$ 。类似添加边集 $E^{'}$ 为 $G + E^{'}$ 。
在图 $G$ 中添加一个新的顶点 $u$ ，得到的图记作 $G + u$ 。类似添加顶点集 $V^{'}$ 为 $G + V^{'}$ 。

2.7.2 交和并

不交：两图点集无交集。
边不交：两图边集无交集。
并图： $G_1 \cup G_2$ ，若两图不交，也记作 $G_1+G_2$ 。
交图： $G_1 \cap G_2$ 。

2.7.3 收缩和剖分

收缩：设 $e = uv$ 是图 $G$ 的一条连杆，去掉 $e$ ，把顶点 $uv$ 合并为一个新的顶点。图 $G$ 中一切与 $uv$ 相连的边都改为与新顶点关联，其他顶点和边不变。图记作 $G \cdot e$ 。
剖分：指去掉边 $e$ ，用一条连接 $e$ 的两个端点的长为 $2$ 的链代替。

2.7.4 笛卡尔积

笛卡尔积： $G_1、G_2$ 的笛卡尔积，记作 $G_1 \times G_2$ 。顶点集为 $V_1 \times V_2$ 。新图两个顶点相连当且仅当 $v_{1i},v_{2j})$ 和 $v_{1k},v_{2l})$ 中的 $v_{1i}=v_{1k}$ 且 $v_{2j}v_{2l} \in E_2$ 。
笛卡尔积可以构造立体图(升维)。

3 树及其算法

3.1 树和森林

3.1.1 树的基本概念

树：连通且不含圈的图，常用 $T$ 来表示。
森林：不含圈的图称为无圈图，也称为森林。

3.1.2 破圈法和避圈法

支撑树：图 $G$ 的支撑子图。
定理：图 $G$ 有支撑树当且仅当 $G$ 连通。
破圈法和避圈法是化图为树的方法。

3.1.3 六个等价命题

定理：设 $T$ 是 $v$ 阶图，下列命题等价：

$T$ 是树。
$T$ 是无环图，且 $T$ 的任何两个顶点间有唯一一条链。
$T$ 是无圈图，且有 $v - 1$ 条边。
$T$ 是连通图，且有 $v - 1$ 条边。
$T$ 是连通图，但 $\forall e \in E(T)$ ， $T - e$ 是非连通图。
$T$ 是连通图，但添加任何一条边后得到的图中都含有唯一的圈。

证明：

$1 - > 2 :$ $T$ 是树推导 $T$ 是无环图，且 $T$ 的任何两个顶点间有唯一一条链。
设 $T$ 是树，显然 $T$ 中无环。假设 $T$ 中存在两条不同的 $v_1,v_2)$ 链 $P_1,P_2$ ，则有边 $\in E(P_1)且\notin E(P_2)$ 。
设 $P_1$ 上的 $v_1,x)$ 节与 $P_2$ 的最后一个公共顶点为点 $u$ ， $P_1$ 上的 $y,v_2)$ 节与 $P_2$ 的第一个公共顶点为 $w$
$P_1$ 的 $(u, w)$ 节 $Q_1$ 与 $P_2$ 的 $(u, w)$ 节 $Q_2$ 无公共内部点，从而 $Q_1Q_2^{-1}$ 是 $T$ 的一个圈。
$2 - > 3 :$ $T$ 是无环图，且 $T$ 的任何两个顶点间有唯一一条链推导 $T$ 是无圈图，且有 $v - 1$ 条边
设 $T$ 满足 $2$ ，则 $T$ 是无圈图。下面对 $T$ 的阶数 $v$ 用归纳法证明 $\varepsilon(T)=v-1$ 。
当 $v = 1$ 时， $T$ 是空图，结论成立。
当 $v < k$ 时结论成立。
现设 $v=k\geq 2$ 时， $v_1v_2 \in E(T)$ ，则 $T-v_1v_2$ 中不含 $v_1,v_2)$ 链，从而 $T-v_1v_2$ 是非连通图，则含有两个连通分支 $T_1$ 和 $T_2$ 。
因为 $T$ 是无圈图，所以 $T_1,T_2$ 也都是无圈图，都是树，因此 $T_1,T_2$ 都满足 $2$ 。
由归纳假设 $\varepsilon(T_i) = v(T_i)-1(i=1,2)$ 。
于是有 $\varepsilon(T)=\varepsilon(T_1)+\varepsilon(T_2)+1=v(T_1)+v(T_2)-1=v(T)-1$ 。
因此成立。
$3 - > 4 :$ $T$ 是无圈图，且有 $v - 1$ 条边推导 $T$ 是连通图，且有 $v - 1$ 条边
设 $T$ 满足 $3$ ，则只需证明 $T$ 连通。
（反证法）假设 $T$ 的连通分支为 $T_1,T_2,...,T_k，k \geq 2$ ，易见 $T_i(i=1,2,..,k)$ 为树。
由一直 $\varepsilon(T_i)=v(T_i)-1(i=1,2,...,k)$ ，因此 $\varepsilon(T)=\sum_{i=1}^{k}\varepsilon(T_i)=\sum_{i=1}^{k}(v(T_i) - 1)=v(T)-k<v(T)-1$ 。这与 $\varepsilon(T)=v(T)-1$ 相矛盾。
$4 - > 5 :$ $T$ 是连通图，且有 $v - 1$ 条边推导 $T$ 是连通图，但 $\forall e \in E(T)$ ， $T - e$ 是非连通图。
设 $T$ 满足 $4$ ，只需证明 $\forall e \in E(T),T-e$ 是非连通图。
假若 $T - e$ 连通：
当 $T - e$ 不含圈时， $T - e$ 是树，此时 $\varepsilon(T-e)=v(T-e)-1$
当 $T - e$ 含圈时，由破圈法可知， $\varepsilon(T-e)>v(T-e)-1$
因此总有 $\varepsilon(T)=\varepsilon(T-e)+1\geq v(T-e)=v(T)$ ，此与 $\varepsilon(T)=v(T)-1$ 矛盾。
$5 - > 6 :$ $T$ 是连通图，但 $\forall e \in E(T)$ ， $T - e$ 是非连通图推导 $T$ 是连通图，但添加任何一条边后得到的图中都含有唯一的圈
设 $T$ 满足 $5$ ，则 $T$ 是无圈图，则是树。
假若添加新边 $e = x y, T + x y$ 不含圈，则 $T + x y$ 是树，于是 $\varepsilon(T+xy)=v(T+xy)-1=v(T)-1$ ，故 $\varepsilon(T)=\varepsilon(T+xy)-1=v(T)-2$ ，这与树矛盾，所以 $T + x y$ 含有圈。
因 $T$ 中不含圈，故 $T + e$ 中任何圈 $C$ 都必含有边 $e$ ，则 $C - e$ 是 $T$ 中的 $(x, y)$ 链。
又由 $2$ 知 $T$ 只有一条 $(x, y)$ 链，因此圈 $C$ 唯一。
$6 - > 1 :$ $T$ 是连通图，但添加任何一条边后得到的图中都含有唯一的圈推导 $T$ 是树
设 $T$ 满足 $6$ ，只需证明 $T$ 连通。
假若 $T$ 是非连通图，任取两个连通分支 $T_1$ 和 $T_2$ ，设 $v_i \in V(T_i),i=1,2$ ，则 $T+v_1v_2$ 不含圈，这与 $6$ 矛盾。因此得证。

推论：若树 $T$ 的阶数 $\geq 2$ ，则 $T$ 至少含有两个悬挂点。
证明：假设 $T$ 至多有一个悬挂点。因为 $\geq 2$ ，所以 $T$ 中每个顶点的度都不为 $0$ .
所以 $\sum_{v \in V(T)}d(v)\geq 1+2(v(T)-1)=2v(T)-1$ ，而由握手引理知 $\sum_{v \in V(T)} d(v) = 2\varepsilon(T)=2v(T)-2$ ，因此矛盾。
推论：设 $G$ 有 $v$ 个顶点， $\varepsilon$ 条边， $\omega$ 个连通分支，则 $G$ 是森林当且仅当 $\varepsilon=v-\omega$ 。
证明：假若 $G$ 不是森林，则 $G$ 中含有圈，至少 $G$ 中存在一个连通分支含有圈，于是根据上边 $4 - > 5$ 的证明，对于任何含圈的连通分支 $G_i$ ，都有 $\varepsilon(G_i) > v(G_i) - 1$ 。因此 $\varepsilon=\sum_{k=1}^\omega\varepsilon(G_k)>\sum_{k=1}^\omega(v(G_k)-1)=v-\omega$ ，因此矛盾。

3.2 支撑树的计数

3.2.1 递推公式

定理：设 $e$ 是 $G$ 的连杆，则 $\tau(G)=\tau(G-e)+\tau(G·e)$ 。
证明：把 $G$ 的支撑树分为两类：第一类含有边 $e$ ，第二类不含边 $e$ 。显然，第二类支撑树计数 $\tau(G-e)$ 。
设 $T$ 是第一类支撑树，注意到 $T \cdot e$ 仍然是树，是 $G \cdot e$ 的支撑树。只要把 $e$ 收缩得到的顶点用 $v_1ev_2$ 代替，即可得到含边 $e$ 的支撑树，从而和 $\tau(G-e)$ 对应上。

3.2.3 矩阵-树定理

设 $G$ 为非空无环连通图，则 $\tau(G)=|L_i(G)|$ ，其中 $L_i(G)$ 表示删去 Laplace 矩阵第 $i$ 行和第 $i$ 列得到的矩阵。

3.3 树上顶点和边的性质

3.3.1 割边

割边： 图 $G$ 中使 $\omega(G-e) > \omega(G)$ 的边 $e$ 。
引理： $\forall e \in E(g)$ ，有 $\omega(G) \leq \omega(G-e) \leq \omega(G) + 1$
定理： $\in E(g)$ 是图 $G$ 的割边，当且仅当 $e$ 不在 $G$ 的任何圈上。
证明：

设 $e$ 是 $G$ 的割边，则 $\omega(G-e)>\omega(G)$ ，从而存在 $G$ 的两个顶点 $u, v$ 在 $G$ 中连通而在 $G - e$ 中不连通。因此 $G$ 中必有一条 $(u, v)$ 链 $P$ 经过 $e$ 。
设 $e = x y$ ，并且在 $P$ 上 $x$ 位于 $y$ 之前，记 $P$ 的 $(u, x)$ 节为 $P_1$ ， $P$ 的 $(y, v)$ 节为 $P_2$ 。若 $e$ 在 $G$ 的某个圈 $C$ 上，则 $C - e$ 是 $G - e$ 中的 $(x, y)$ 链 $Q$ ，从而 $P_1QP_2$ 是 $G - e$ 中一条 $(u, v)$ 途径，于是 $u, v$ 在 $G - e$ 中连通，矛盾。
假设 $e = x y$ 不是 $G$ 的割边，则由引理知 $\omega(G)=\omega(G-e)$ 。因为边 $x y$ 是 $G$ 的一条 $(x, y)$ 链，因此 $x, y$ 在 $G$ 的同一连通分支中，故也在 $G - e$ 的连通分支中，即 $(x, y)$ 存在其他链 $P$ ，于是 $P + e$ 是 $G$ 中的圈，包含边 $e$ 。

3.3.2 边割

边割： $[S,S']=\{uv \in E(G) | u \in S, v \in S'\}。$ 若 $\subset V(G),S \neq \emptyset,\overline{S} = V(G)$ \ $S$ ，且 $[S,\overline{S}] \neq \emptyset$ ，则称 $[S,\overline{S}]$ 为 $G$ 的边割。
极小边割/补圈/余圈：若边割的任意真子集都不再是边割，那该边割为极小边割。
定理：设 $G$ 为连通图，则 $G$ 的边割 $[S, S^{'}]$ 是补圈 <==> $G [S]$ 和 $G [S^{'}]$ 都连通。

证明：

后推前：因为 $G [S]$ 和 $G[\overline{S}]$ 都连通，所以从连通图 $G$ 删去 $[S,\overline{S}]$ 的任何一个真子集后得到的图仍连通，因此 $[S,\overline{S}]$ 是 $G$ 的补圈。
前推后：设 $[S,\overline{S}]$ 是连通图 $G$ 的补圈，若 $G [S]$ 不连通，设 $H$ 是 $G [S]$ 的一个连通分支，则 $[V (H), V (G)$ \ $V (H)]$ 是边割，且是 $[S,\overline{S}]$ 的真子集，这与 $[S,\overline{S}]$ 是极小边割矛盾。若 $G[\overline{S}]$ 不连通，同理，也可以得到矛盾。

推论：设 $[S, S^{'}]$ 为图 $G$ 的一个边割，则 $[S, S^{'}]$ 或者是补圈，或者是一些两两不交的补圈的并。
证明：

$G$ 是连通的：如果 $G[S],G[\overline{S}]$ 都连通，则由定理知 $[S,\overline{S}]$ 是补圈。如果 $G [S]$ 和 $G[\overline{S}]$ 不都连通，设 $G [S]$ 不连通，记 $G [S]$ 的连通分支为 $H_1,H_2...,H_n$ ，设 $G-V(H_i)$ 的连通分支为 $G_{i1},G_{i2},...,G_{ir_i}(i=1,2,...,n)$ 。由于 $G$ 连通，因此 $H_i$ 与各个 $G_{ij}(1 \leq j \leq 2)$ 都有边相连，从而 $G[\overline{V(G_{i,j})}]$ 连通 $(1\leq i \leq n, 1 \leq j \leq r_j)$ 。由定理知 $[\overline{V(G_{ij}}),V(G_{ij})]$ 是 $G$ 的补圈，显然，这些补圈互不相交，并且…………
$G$ 是非连通的。令 $G$ 的连通分支 $G^{(1)},G^{(2)},...,G^{(\omega)}$ ， $S_k=S \cap V(G^{k})$ ， $\overline{S_k}=V(G)$ \ $k=1,2,...,\omega$ ，显然 $[S,\overline{S}]$ = $\cup_{k=1}^{\omega}[S_k, \overline{S_k}]$ . …

补树： 设 $G$ 是连通图， $T$ 是 $G$ 的一个支撑树，则称补图 $\overline{T}(G)$ 为 $G$ 的补树，记作 $\overline{T}$ 。
定理：设 $T$ 是连通图 $G$ 的支撑树， $\in E(T)$ ，则（1）补树 $T$ 不含有任何极小边割。（2） $T + e$ 中含有唯一的极小边割。
证明：（1）设 $[S,\overline{S}]$ 是 $G$ 的一个极小边割，则 $G-[S,\overline{S}]$ 不连通，因而 $G-[S,\overline{S}]$ 不包含树 $T$ ，即存在 $e_0 \in E(T)$ 但 $e_0 \notin G-[S,\overline{S}]$ ，于是 $e_0 \in [S, \overline{S}]$ ，故 $\overline{S}]$ 不包含在 $\overline{T}$ 中。（2）设边集 $E_0$ 是包含于 $\overline{T} + e$ 中唯一极小边割，则 $T - e$ 包含在 $G-E_0$ 中。 $\forall b \in [V(T_1),V(T_2)]$ ，假若 $\notin E_0$ ，则 $T - e + b$ 包含于 $G-E_0$ 。注意到 $T - e + b$ 连通图且 $\varepsilon(T-e+b)=v(T)-1$ ，故 $T - e + b$ 是 $G$ 的支撑树，即 $G-E_0$ 中包含连通子图 $T - e + b$ 与 $G-E_0$ 不连通矛盾， $\in E_0$ ，由 $E_0$ 是极小边割可知 $E_0=[V(T_1),V(T_2)]$ ，于是 $\overline{T}+e$ 中包含 $G$ 的唯一极小边割。

3.3.3 割点

割点：如果图 $G$ 的边集 $E$ 可以分划成两个非空子集 $E_1、E_2$ ，如果 $G[E_1]、G[E_2]$ 有唯一公共顶点 $v$ ，则称 $v$ 为图 $G$ 的割点。
引理：若顶点 $v$ 满足 $\omega(G-v) > \omega(G)$ ，则 $v$ 是图 $G$ 的割点。（不满足也可能是割点）反之，若 $G$ 的割点 $v$ 上无环，则 $\omega(G-v) > \omega(G)$ 。
证明：

设顶点 $v$ 满足 $\omega(G-v) > \omega(G)$ ，且 $v$ 是 $G$ 连通分支 $H$ 中的顶点，把 $H - v$ 的连通分支记为 $H_1,H_2,...,H_k$ ，由假设知 $\geq 2$ ，令 $E_1=E(H_1)\cup\{uv\in E(H) | u \in V(H_1)\}$ ， $E_2=E(G)$ \ $E_1$ 。显然 $E_1,E_2$ 是 $G$ 的一个划分，且不为空集，有唯一公共顶点 $v$ ，从而 $v$ 是 $G$ 的割点。
设 $v$ 是 $G$ 的割点，且无环。 $v$ 是 $G[E_1],G[E_2]$ 的唯一公共顶点，注意划分为非空划分。故存在连杆 $vu_1 \in E_1, vu_2 \in E_2$ ，即 $u_1,u_2$ 存在于同一个连通分支中。因此所有 $u_1,u_2)$ 链必定经过 $v$ ，于是 $u_1,u_2$ 在 $G - v$ 的不同连通分支，即 $\omega(G-v)>\omega(G)$ 。

若 $G$ 的割点 $v$ 有环，则 $\omega(G-v)>\omega(G)$ 不一定成立

定理：树 $T$ 的顶点 $v$ 是割点，当且仅当 $d (v) > 1$ 。
证明：

若 $d (v) = 0$ ，则该图是 $1$ 阶完全图，故 $v$ 不是割点。若 $d (v) = 1$ ，则 $T - v$ 仍是无圈图，且有 $\varepsilon(T)-1$ 条边，从而有 $v (T) - 2 = v (T - v) - 1$ 条边， $T - v$ 是树，所以 $\omega(T-v)=\omega(T)$ ，由引理知 $v$ 不是割点。
若 $d (v) > 1$ ，则 $T$ 中存在两个相异顶点 $u, w$ 与 $v$ 相邻，链 $uv w$ 是 $T$ 中唯一 $(u, w)$ 链，由此知 $T - v$ 中不再有 $(u, w)$ 链，故 $\omega(T-v)>\omega(T)$ ，知 $v$ 是 $G$ 的割点。

3.4 最小支撑树

3.4.1 最小支撑树的定义

树 $T$ 的权： $\sum_{e \in E(T)} w(e)$ 。
最小支撑树：权最小的支撑树。

3.4.2 Prim 算法

算法流程略
定理：设 $G$ 是连通加权图，由 $P r im$ 算法构造的支撑树一定是图 $G$ 的最小支撑树。

3.4.3 Kruskal 算法

算法流程略
定理：设 $G$ 是连通加权图，由 $Kr u s ka l$ 算法构造的支撑树一定是图 $G$ 的最小支撑树。

3.5 二叉树与前缀码

3.5.1 二元树

二元树：设 $T$ 是一个树，每个边都规定一个方向，若存在一个入度为 $0$ 的顶点 $v_0$ ，其他顶点 $v$ 的入度都为 $1$ ，则称 $T$ 为根树， $v_0$ 为根，出度为 $0$ 的点为叶子。
$n$ 元树：设 $T$ 为根树， $\forall v \in V(T), d^+(v) \leq n$ ，则为 $n$ 元树。若都有 $n$ 个儿子，则称为典型 $n$ 元树。
有序树：若根数的每个顶点的儿子们有序，称为有序树。
定理：由 $2 n$ 个括号组成的好括号列个数是： $\frac1{n+1}C_{2n}^{n}$ 。

3.5.2 前缀码

前缀码：在一个序列集合中，如果任何一个序列都不是另一个序列的前缀，则称这个集合为前缀码。

3.5.3 Huffman树

Huffman树：以 $v_0$ 为根，以 $v_1,v_2,....,v_n$ 为叶子的有序二元树中，称 $v_0,v_i)$ 链的长 $l_i$ 为叶子 $v_i$ 的码长。
最优二元树：使得 $m(T)=\sum_{i=1}^{n}p_il_i$ 达最小的 $H u ff man$ 树。文章来源地址https://www.toymoban.com/news/detail-739522.html