图论 | 期末复习笔记 |（二）

边加权属于P问题，点加权属于NP问题

等价定义：设 $G =< V, E >$ 是 $n$ 阶 $m$ 条边的简单无向图，则下面各命题是等价的：
1. $G$ 是树且连通无圈
2. $G$ 中任意两个顶点之间存在唯一的路径
3. $G$ 中无圈且 $m = n - 1$
4. $G$ 是连通的且 $m = n - 1$
5. $G$ 是连通的且 $G$ 中任何边均为桥
6. $G$ 中无圈，但在任何两个不相邻的顶点之间加一条新边，所得图中得到唯一的一个含新边的圈
推论：具有 $k$ 个分支的森林有 $n - k$ 条边，其中 $n$ 是 $G$ 的顶点数。
性质：设 $T$ 是 $n$ 阶非平凡的无向树，则 $T$ 中至少有两片树叶，即至少有两个一次顶点。
$2(n-1)=\sum d(v_i)\geqslant x+2(n-x)\\ x\geqslant2$

引理：每颗恰有两个一次顶点的树均是路。（反证法）
设 $G$ 是森林（树）且恰有 $2 k$ 个奇次顶点，则在 $G$ 中有 $k$ 条边不重和的路 $P_1,P_2,\ldots,P_k$ ，使得 $E(G)=E(P_1)\cup E(P_2)\cup\cdots\cup E(P_k)$ 。（数学归纳法）
设 $T$ 是 $k$ 阶树，若图 $G$ 是满足 $\delta\geqslant k-1$ 的简单图，则 $T$ 同构于 $G$ 的某个子图。（数学归纳法）

设 $S=\{d_1,d_2,\ldots,d_n\}$ 是 $n$ 个正整数序列，满足 $d_1\geqslant d_2\geqslant \cdots\geqslant d_n,\sum d_i=2(n-1)$ ，则存在一棵树 $T$ ，其度序列为 $S$ 。（数学归纳法）

设 $G$ 为无向图，
1. $T$ 为 $G$ 的树—— $T$ 是 $G$ 的子图并且是树。
2. $T$ 为 $G$ 的生成树—— $T$ 是 $G$ 的生成子图并且是树。
3. $e$ 为 $T$ 的树枝——设 $T$ 为 $G$ 的生成树， $\forall e\in E(G)$ ，若 $e\in E(T)$ 。
4. $e$ 为 $T$ 的弦——设 $T$ 为 $G$ 的生成树， $\forall e\in E(G)$ ，若 $e\notin E(T)$ 。
5. 生成树 $T$ 的余树——导出子图 $G [E (G) - E (T)]$ ，记作 $\bar{T}$ 。
注意： $\bar{T}$ 不一定连通，也不一定不含回路。
定理：无向图 $G$ 具有生成树当且仅当 $G$ 连通。
例：连通图 $G$ 的无圈子图 $T$ 是 $G$ 的某个生成树的子图。
定理：设 $T$ 是无向连通图 $G$ 的一棵生成树， $e$ 为 $T$ 的任意一条弦，则 $T\cup\{e\}$ 中存在只含一条弦 $e$ ，其他边均为树枝的圈，而且不同的弦对应的圈不同。

设无向图 $G =< V, E >$ ，若存在 $E'\subseteq E$ ，且 $E'\neq\varnothing$ ，使得 $\omega(G-E')>\omega(G)$ ，则称 $E^{'}$ 是 $G$ 的边割集。若 $E^{'}$ 是 $G$ 的边割集，且对于任意的 $E''\subset E'$ ，均有 $\omega(G-E'')=\omega(G)$ ，则称 $E^{'}$ 是 $G$ 的极小边割集。
设无向图 $G =< V, E >$ ，若存在 $V'\subseteq V$ ，且 $V'\neq\varnothing$ ，使得 $\omega(G-V')>\omega(G)$ ，则称 $V^{'}$ 是 $G$ 的点割集。若 $V^{'}$ 是 $G$ 的点割集，且对于任意的 $V''\subset V'$ ，均有 $\omega(G-V'')=\omega(G)$ ，则称 $V^{'}$ 是 $G$ 的极小点割集。
注意：如果 $G$ 是连通图， $V_1,V_2)$ 是 $V$ 的划分，设 $V_1,V_2]$ 表示从 $V_1$ 中的点到 $V_2$ 中的点的所有边，则 $V_1,V_2]$ 是边割集。
定理：设 $T$ 是无向连通图 $G$ 的一棵生成树， $e$ 为 $T$ 的任意树枝，则 $G$ 中存在只含树枝 $e$ 其他边都是弦的割集，且不同树枝对应的割集不同。

设 $G$ 是连通图， $T, T^{'}$ 是 $G$ 的两个生成树，如 $E (T)$ 与 $E (T^{'})$ 不同，就是两个不同的生成树，个数记为 $\tau(G)$ 。
Cayley定理：设 $e$ 是连通图 $G$ 的一条边，则有 $\tau(G)=\tau(G-e)+\tau(G\circ e)$ ，收缩边。

$\tau(K_n)=n^{n-2}$ .

若 $e$ 为 $K_n$ 的一条边，则 $\tau(K_n-e)=(n-2)n^{n-3}$ 。

证明： $K_n$ 所有生成树的总边数为 $n-1)n^{n-2}$ ，每条边对应的生成树的棵数为 $\frac{(n-1)n^{n-2}}{\frac{1}{2}n(n-1)}=2n^{n-3}$ ，所以 $K_n-e$ 对应的生成树的棵数为 $\tau(K_n-e)=n^{n-2}-2n^{n-3}=(n-2)n^{n-3}$ 。

树的每边规定一个方向且使得任意的 $v_i\in V(T)$ ，存在有向道路 $P(v_0,v_i)$ ，则称 $T$ 的外向树， $v_0$ 叫做根，反之则称为内向树。
$T$ 为外向树，对任意的顶点 $v\in V(T)$ ，都有 $d^+(v)\leqslant\sigma$ ，则称 $T$ 为 $\sigma$ 元树。
除叶子外，每顶点皆有 $\sigma$ 子时，称为典型 $\sigma$ 元树。
在 $v_0$ 为根， $v_1,v_2,\ldots,v_n$ 为叶的有序二元树中，路径 $P(v_0,v_i)(i=1,2,\ldots,n)$ 的长度 $l_i$ 叫做叶 $v_i$ 的码长。若 $v_i(i=1,2,\ldots,n)$ 代表的事物出现的概率为 $p_i,\sum_{i=1}^{n}p_i=1$ ，使得 $m(T)=\sum_{i=1}^{n}p_il_i=min$ 的有序二元树 $T$ 叫做带权 $p_1,p_2,\ldots,p_n$ 的Huffman树，也叫做最优二叉树。Huffman树的前缀编码称为Huffman编码。
Huffman算法