树的有关定义 口定义3.13 如果T是图G的支撑子图而且又是一棵树则称T是 G的一棵支撑树,或称生成树,又简称G的树
树的有关定义 定义3.1.3 如果T是图G的支撑子图, 而且又是一棵树, 则称T是 G的一棵支撑树, 或称生成树, 又简称G的树
生成树 定理:任何无向连通图G都存在生成树 证明:如果G无回路,则G本身就是它的生成树。 如G有回路,则在回路上任取一条边去掉仍是连通 的,如G仍有回路,则继续在该回路上去掉一条边, 直到图中无回路为止,此时,该图就是G的一棵生 成树
定理：任何无向连通图G都存在生成树。 证明：如果G无回路，则G本身就是它的生成树。 如G有回路，则在回路上任取一条边去掉仍是连通 的，如G仍有回路，则继续在该回路上去掉一条边， 直到图中无回路为止，此时，该图就是G的一棵生 成树。 生成树
一个连通图的生成树可能不唯 因为在取定一个回路后,就可以从中去掉任一条边, 去掉的边不一样,故可能得到不同的生成树。 6 b 5 d 4 4 a 2 (a) b 在上图(a)中,删去边2,3,5,就得到生成树(b), 若删去边2,4,6,可得到生成树(c)
一个连通图的生成树可能不唯一。 因为在取定一个回路后，就可以从中去掉任一条边， 去掉的边不一样，故可能得到不同的生成树。 在上图(a)中，删去边2,3,5，就得到生成树 (b)， e d c 3 c e d e d c 若删去边2，4，6,可得到生成树 (c)
生成树 b b○ b) (c) 给定图G的一棵树T,我们称GT,即G删去T中各边后的子 图为T的余树。 注:余树不一定连通,也不一定无回路,因而余树不一定是 树,更不一定是生成树
生成树 给定图G的一棵树T，我们称G-T，即G删去T中各边后的子 图为T的余树。 注：余树不一定连通，也不一定无回路，因而余树不一定是 树，更不一定是生成树。 a b c d e (a) a b c d e (b) f f (c) a c d e b f
36 Huffman树 口定义361 除树叶外其余结点的正度最多为2的外向 树称为二又树。如果它们的正度都是2,称为 完全二叉树 外向树-若一个有向树T,有 且只有一个顶点入度为0,其 Ov2 余顶点入度都为1,则称T为外 向树,其中入度为0的节点称 ⑥caak6 5 为根节点,出度为0的节点称 V3 v4 a 为叶节点 v7 v8
3.6 Huffman树 定义3.6.1 除树叶外, 其余结点的正度最多为2的外向 树称为二叉树. 如果它们的正度都是2, 称为 完全二叉树. a v5 v7 v8 v6 d e v2 b v3 v1 c v4 v0 外向树--若一个有向树T，有 且只有一个顶点入度为0，其 余顶点入度都为1，则称T为外 向树，其中入度为0的节点称 为根节点，出度为0的节点称 为叶节点