7.1 无向树及生成树

先来看一些基本概念：

简单来说就是由多颗数组成的。

来看一些定理：

如果我们让树中的每一条与其下方的结点对应，那么最后多出来一个根节点。故在树中，边数等于结点数减去1。

定理2：

例题：

解析：
由上可知，树中结点数减去1就是边数，边数乘以2就是总度数。根据这个可以列方程求解。

生成树：删回路，直到出现树
弦：把生成树抠掉剩下的边角料
余树：边角料的集合

注意：

• 余树可以不连通，且可能含有回路。
• 生成树一般不是唯一的，只有当图是一棵树时，其生成树才是唯一的。（也就是说：生成树的唯一性不确定）

我们来看最小生成树：

来看一个算法：

例题：

---

弦的基本回路：
对于每一条弦$e$e，存在唯一的由弦$e$e和生成树的树枝构成的初级回路$C_e$Ce​，称$C_e$Ce​为对应于弦$e$e的基本回路。所以基本回路的集合称为生成树$T$T的基本回路系统。

eg：

$C_a$Ca​ = aed
$C_b$Cb​ = bdf
$C_c$Cc​ = cef

基本回路系统为：
{$C_a$Ca​，$C_b$Cb​，$C_c$Cc​}

---

树枝的基本割集：
对于生成树的每一个树枝$a$a，存在唯一的由树枝$a$a其余边都是弦的割集$S_a$Sa​，称$S_a$Sa​为对应树枝$a$a的基本割集，称所有基本割集的集合为对应生成树$T$T的基本割集系统。

eg：

$S_a$Sa​ = {a,g,f}
$S_b$Sb​ = {b,g,h}
$S_c$Sc​ = {c,f,h}
$S_d$Sd​ = {d,h,i}
$S_e$Se​ = {e,f,i}

基本割集系统为{$S_a$Sa​，$S_b$Sb​，$S_c$Sc​，$S_d$Sd​，$S_e$Se​}

---

合并：操作方法就是将$C_i$Ci​和$C_j$Cj​中相同的删除再合并起来。

eg;

易得：
$C_f$Cf​ = face
$C_g$Cg​ = gba
$C_h$Ch​ = hdcb
$C_i$Ci​ = ied

$C_f$Cf​ $\bigoplus$⨁ $C_g$Cg​ = fgbce
$C_f$Cf​ $\bigoplus$⨁ $C_h$Ch​ = fabhde

$\cdots$⋯

---

练习1：
设图G是有6个顶点的连通图,总度数为20,则从G中删去()条边后使之变成树?

练习2：
设G是一棵树，则G的生成树有()棵?

答案：1

练习3：
设G是一棵无向树，则G一定是()?


解析：
让树的每一层的点交替属于$v_1$v1​,$v_2$v2​即可。

练习4：