图论与网络优化

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

1. 【笔记1】概念与计算、树及其算法
2. 【笔记2】容量网络模型、遍历性及其算法
3. 【笔记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_i{v}_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\epsilon$。
例题：空间中不存在有奇数个面并且每个面只有奇数个棱的多面体。
思路：将面抽象为点，两面之间的棱为边，则转化成了有奇数个点且每个点都是奇数度的图，与握手引理矛盾，得证。

例题：证明非负整数序列 $(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\ge d_2\ge ...\ge d_v)$ 是图序列当且仅当 ${\sum }_{i=1}^v{d}_i$ 是偶数，并且对一切整数 $k(1\le k\le v-1$，有 ∑ i = 1 k ≤ k ( k − 1 ) ≤ ∑ i = k + 1 v m i n { k , d i } \sum_{i=1}^{k} \leq k(k-1) \leq \sum_{i=k+1}^{v}min \{k,d_i\} ∑i=1k​≤k(k−1)≤∑i=k+1v​min{k,di​}.
例题：$(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$ 为两个图。若 $V(H)\subseteq V(G)$ 且 $E(H)\subseteq E(G)$，则 $H$ 为 $G$ 的子图。记作 $H\subseteq G$。
相等：设 $H$ 和 $G$ 为两个图。若 $V(H)=V(G)$ 且 $E(H)=E(G)$，则 $H$ 为 $G$ 相等。记作 $H=G$。
真子图：若 $H\subseteq G$ 且 $H\ne G$，则称 $H$ 是 $G$ 的真子图，记作 $H\subset G$。
支撑(生成)子图：若 $V(H)=V(G)$ 且 $E(H)\subseteq E(G)$，则称 $H$ 是 $G$ 的支撑子图或生成子图。
基础简单图：对图 $G$ 去除重边和环后的图 $H$。

---

2.2.2 导出子图

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

---

2.2.3 连通分支

途径的起点/终点/长度/逆转/衔接/节：$W=v_o{e}_1{v}_1{e}_2...e_k{v}_k$，这里 $v_i\in V(0\le i\le k),e_j=v_{j-1}{v}_j\in E(1\le j\le 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$ 中至少有一对顶点不相邻，证明存在 $u,v,w\in V$，使 $uv,vw\in E$，但 $uw\notin E$。
思路：设 $x,y\in V$ 且 $xy\notin E$。因 $G$ 连通，故 $G$ 中存在最短 $(x,y)$ 链 $P=x{v}_1{v}_2...y$。
由 $P$ 的最短性可知 $x{v}_2\notin E$，于是令 $u=x,v=v_1,w=v_2$，则有$uv\in E,vw\in E$ 但 $uw\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$ 为偶数，当 $n\ge k+1$，$n$ 阶 $k$ 正则图存在吗？
思路：
${\gamma }_1$ 法则：构造偶数正则图法则。
设 $G$ 是 $v$ 阶 $k$ 正则图，且 $k=2m$，$m\ge 1$，按以下步骤生成新图 $G^{\prime }$：
step 1：在图 $G$ 中任取 $m$ 条互不相邻的边：$v_1{v}_2,v_3{v}_4,...,v_{2m-1}{v}_{2m}$ 并删除。
step 2：增加新的顶点 $v$，并向所有被删边的点增加一条新边 $v{v}_i(i=1,2,...,2m)$，得到新图 $G^{\prime }$。

${\gamma }_2$ 法则：构造奇数正则图法则。
设 $G$ 是 $v$ 阶 $k$ 正则图，且 $k=2m+1$，$m\ge 1$，按以下步骤生成新图 $G^{\prime }$：
step 1：在图 $G$ 中任取 $m$ 条互不相邻的边：$v_1{v}_2,v_3{v}_4,...,v_{2m-1}{v}_{2m}$ 并删除。
step 2：再在图 $G$ 中任取 $m$ 条互不相邻的边：$u_1{u}_2,u_3{u}_4,...,u_{2m-1}{u}_{2m}$ 并删除。
(step 1 和 step 2 中可能会出现重复点)
step 3：增加新的顶点 $w_1$，并向 step 1 中所有被删边的点增加一条新边 $w_1{v}_i(i=1,2,...,2m)$。
step 4：再增加新的顶点 $w_2$，并向 step 2 中所有被删边的点增加一条新边 $w_2{u}_i(i=1,2,...,2m)$。
step 5：加边 $w_1{w}_2$，得新图 $G^{\prime }$。

定理：$n$ 阶 $k$ 正则简单图存在的充要条件是 $k\le n-1$ 且 $nk$ 为偶数。
证明：设 $G$ 是 $n$ 阶 $k$ 正则简单图，每个顶点最多与其他 $n-1$ 个顶点相邻，因此 $k\le n-1$ 成立。
设 $k=2m$，取 $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_0{v}_1...v_k{v}_0)$ 是 $G$ 中的一个圈，长度为 $k+1$。
设 $v_0\in X$，于是后面节点依次属于 $Y$ 和 $X$。因此得到 $v_{2i}\in X，v_{2i+1}\in Y$。
因此 $k=2l+1$。该圈为偶圈。
step 2：
设 $G$ 连通(若不连通则取一个连通分支证明之)。在 $G$ 中任取一个顶点 $u$，令 X = { x ∣ d ( u , x ) 为偶数 } X=\{x|d(u,x)为偶数\} X={x∣d(u,x)为偶数}， Y = { y ∣ d ( u , y ) 为奇数 } Y=\{y|d(u,y)为奇数\} 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}_{1}wv$ 就是 $G$ 中的一个奇圈，与假设矛盾。

---

2.4 有向图

2.4.1 定义

有向图：有向图 $D$ 指一个有序三元组 $(V(D),A(D),{\psi }_D)$，其中 $V(D)\ne \varnothing$，$V(D)\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)=\epsilon (D)$

2.4.4 回路

有向途径：$W=v_0{a}_1{v}_1{a}_2...v_{k-1}{a}_k{v}_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_1{V}_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})$ 是一个 $v\times v$ 矩阵，$a_{i,j}$ 等于第 $i$ 个顶点与第 $j$ 个顶点的边数。
性质：

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

定理：$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)$。
性质：

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

---

2.6.3 关联矩阵

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

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

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

---

2.7 运算

2.7.1 删去和添加

删去：删边或删点。

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

添加：加边或加点。

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

---

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$ 阶图，下列命题等价：

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

证明：

• $1->2:$ $T$ 是树 推导 $T$ 是无环图，且 $T$ 的任何两个顶点间有唯一一条链。
  设 $T$ 是树，显然 $T$ 中无环。假设 $T$ 中存在两条不同的 $(v_1,v_2)$ 链 $P_1,P_2$，则有边 $e=xy\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_1{Q}_2^{-1}$ 是 $T$ 的一个圈。
  
• $2->3:$$T$ 是无环图，且 $T$ 的任何两个顶点间有唯一一条链 推导 $T$ 是无圈图，且有 $v-1$ 条边
  设 $T$ 满足 $2$，则 $T$ 是无圈图。下面对 $T$ 的阶数 $v$ 用归纳法证明 $\epsilon (T)=v-1$。
  当 $v=1$ 时，$T$ 是空图，结论成立。
  当 $v<k$ 时结论成立。
  现设 $v=k\ge 2$ 时，$v_1{v}_2\in E(T)$，则 $T-v_1{v}_2$ 中不含 $(v_1,v_2)$ 链，从而 $T-v_1{v}_2$ 是非连通图，则含有两个连通分支 $T_1$ 和 $T_2$。
  因为 $T$ 是无圈图，所以 $T_1,T_2$ 也都是无圈图，都是树，因此 $T_1,T_2$ 都满足 $2$。
  由归纳假设 $\epsilon (T_i)=v(T_i)-1(i=1,2)$。
  于是有 $\epsilon (T)=\epsilon (T_1)+\epsilon (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\ge 2$，易见 $T_i(i=1,2,..,k)$ 为树。
  由一直 $\epsilon (T_i)=v(T_i)-1(i=1,2,...,k)$，因此 $\epsilon (T)={\sum }_{i=1}^k\epsilon (T_i)={\sum }_{i=1}^k(v(T_i)-1)=v(T)-k<v(T)-1$。这与 $\epsilon (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$ 是树，此时 $\epsilon (T-e)=v(T-e)-1$
  当 $T-e$ 含圈时，由破圈法可知，$\epsilon (T-e)>v(T-e)-1$
  因此总有 $\epsilon (T)=\epsilon (T-e)+1\ge v(T-e)=v(T)$，此与 $\epsilon (T)=v(T)-1$ 矛盾。
• $5->6:$ $T$ 是连通图，但 $\forall e\in E(T)$，$T-e$ 是非连通图 推导 $T$ 是连通图，但添加任何一条边后得到的图中都含有唯一的圈
  设 $T$ 满足 $5$，则 $T$ 是无圈图，则是树。
  假若添加新边 $e=xy,T+xy$ 不含圈，则 $T+xy$ 是树，于是 $\epsilon (T+xy)=v(T+xy)-1=v(T)-1$，故 $\epsilon (T)=\epsilon (T+xy)-1=v(T)-2$，这与树矛盾，所以 $T+xy$ 含有圈。
  因 $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_1{v}_2$ 不含圈，这与 $6$ 矛盾。因此得证。

推论：若树 $T$ 的阶数 $v\ge 2$，则 $T$ 至少含有两个悬挂点。
证明：假设 $T$ 至多有一个悬挂点。因为 $v\ge 2$，所以 $T$ 中每个顶点的度都不为 $0$.
所以 ${\sum }_{v\in V(T)}d(v)\ge 1+2(v(T)-1)=2v(T)-1$，而由握手引理知 ${\sum }_{v\in V(T)}d(v)=2\epsilon (T)=2v(T)-2$，因此矛盾。
推论：设 $G$ 有 $v$ 个顶点，$\epsilon$ 条边，$\omega$ 个连通分支，则 $G$ 是森林当且仅当 $\epsilon =v-\omega$。
证明：假若 $G$ 不是森林，则 $G$ 中含有圈，至少 $G$ 中存在一个连通分支含有圈，于是根据上边 $4->5$ 的证明，对于任何含圈的连通分支 $G_i$，都有 $\epsilon (G_i)>v(G_i)-1$。因此 $\epsilon ={\sum }_{k=1}^{\omega }\epsilon (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\cdot e)$。
证明：把 $G$ 的支撑树分为两类：第一类含有边 $e$，第二类不含边 $e$。显然，第二类支撑树计数 $\tau (G-e)$。
设 $T$ 是第一类支撑树，注意到 $T\cdot e$ 仍然是树，是 $G\cdot e$ 的支撑树。只要把 $e$ 收缩得到的顶点用 $v_{1}e{v}_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)\le \omega (G-e)\le \omega (G)+1$
定理：$e\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=xy$，并且在 $P$ 上 $x$ 位于 $y$ 之前，记 $P$ 的 $(u,x)$ 节为 $P_1$，$P$ 的 $(y,v)$ 节为 $P_2$。若 $e$ 在 $G$ 的某个圈 $C$ 上，则 $C-e$ 是 $G-e$ 中的 $(x,y)$ 链 $Q$，从而 $P_{1}Q{P}_2$ 是 $G-e$ 中一条 $(u,v)$ 途径，于是 $u,v$ 在 $G-e$ 中连通，矛盾。
• 假设 $e=xy$ 不是 $G$ 的割边，则由引理知 $\omega (G)=\omega (G-e)$。因为边 $xy$ 是 $G$ 的一条 $(x,y)$ 链，因此 $x,y$ 在 $G$ 的同一连通分支中，故也在 $G-e$ 的连通分支中，即 $(x,y)$ 存在其他链 $P$，于是 $P+e$ 是 $G$ 中的圈，包含边 $e$。

---

3.3.2 边割

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

证明：

• 后推前：因为 $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^{\prime }]$ 为图 $G$ 的一个边割，则 $[S,S^{\prime }]$ 或者是补圈，或者是一些两两不交的补圈的并。
证明：

• $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_{i{r}_i}(i=1,2,...,n)$。由于 $G$ 连通，因此 $H_i$ 与各个 $G_{ij}(1\le j\le 2)$ 都有边相连，从而 $G[\overline{V(G_{i,j})}]$ 连通 $(1\le i\le n,1\le j\le 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$ 的支撑树，$e\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}]$，故 $[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)]$，假若 $b\notin E_0$，则 $T-e+b$ 包含于 $G-E_0$。注意到 $T-e+b$ 连通图且 $\epsilon (T-e+b)=v(T)-1$，故 $T-e+b$ 是 $G$ 的支撑树，即 $G-E_0$ 中包含连通子图 $T-e+b$ 与 $G-E_0$ 不连通矛盾，$b\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$，由假设知 $k\ge 2$，令 E 1 = E ( H 1 ) ∪ { u v ∈ E ( H ) ∣ u ∈ V ( H 1 ) } E_1=E(H_1)\cup\{uv\in E(H) | u \in V(H_1)\} E1​=E(H1​)∪{uv∈E(H)∣u∈V(H1​)}，$E_2=E(G)$ \ $E_1$。显然 $E_1,E_2$ 是 $G$ 的一个划分，且不为空集，有唯一公共顶点 $v$，从而 $v$ 是 $G$ 的割点。
• 设 $v$ 是 $G$ 的割点，且无环。$v$ 是 $G[E_1],G[E_2]$ 的唯一公共顶点，注意划分为非空划分。故存在连杆 $v{u}_1\in E_1,v{u}_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$ 仍是无圈图，且有 $\epsilon (T)-1$ 条边，从而有 $v(T)-2=v(T-v)-1$ 条边， $T-v$ 是树，所以 $\omega (T-v)=\omega (T)$，由引理知 $v$ 不是割点。
• 若 $d(v)>1$，则 $T$ 中存在两个相异顶点 $u,w$ 与 $v$ 相邻，链 $uvw$ 是 $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$ 是连通加权图，由 $Prim$ 算法构造的支撑树一定是图 $G$ 的最小支撑树。

---

3.4.3 Kruskal 算法

算法流程略
定理：设 $G$ 是连通加权图，由 $Kruskal$ 算法构造的支撑树一定是图 $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)\le n$，则为 $n$ 元树。若都有 $n$ 个儿子，则称为典型 $n$ 元树。
有序树：若根数的每个顶点的儿子们有序，称为有序树。
定理：由 $2n$ 个括号组成的好括号列个数是：$\frac{1}{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}_i{l}_i$ 达最小的 $Huffman$ 树。

---