7-7 7-7 树与生成树与生成树树幸运树：树：一个一个连通连通且且 无回路无回路的无的无 向图称为树。向图称为树。幸运树叶：树叶：树中树中度数度数 为为1 1的结点的结点 称为树叶。称为树叶。幸运分枝点：分枝点：度数大度数大 于于1 1的结点称的结点称 为分枝点或内为分枝点或内点。点。幸运森林：森林：一个一个无回无回 路的无向图路的无向图称称 作森林，它的作森林，它的 每个每个连通分图连通分图是树。是树。幸运定理定理1 1 给定给定图图T，以下关于树的定以下关于树的定义是等价的。义是等价的。幸运(1)(1)无回路无回路的的连通图连通图。(2)(2)无回路无回路且且e=v-1，其中其中e是边数，是边数，v是结点数。是结点数。(3)(3)连通连通且且e=v-1。(4)(4)无回路无回路，但，但增加增加一条新边，得到一条新边，得到一个且仅有一个且仅有一个回路一个回路。(5)(5)连通连通，但，但删去删去任一边后便任一边后便不连通不连通。(6)(6)每一对结点每一对结点之间有一条且仅有之间有一条且仅有一一条路条路。幸运证明证明（1）（2）设在图设在图T中，当中，当v=2时，连通无回路，时，连
