离散数学(第22讲)(精品·公开课件).pptVIP

计算机学院 计算机科学与工程学院 冯伟森 Email：fws365@scu.edu.cn * * 计算机学院 * 主要内容 树与生成树 Kruskal算法 根树 完全二叉树 Huffman算法 * 计算机学院 * 树 定义11.1　连通而不含圈的无向图称为无向树，简称树。树中度数为1的结点称为树叶；度数大于1的结点称为枝点或内点。常用T表示树。 　　若图G不含圈，则称G为林。 　　若图G是林，则G的每个连通分支都是树。 * 计算机学院 * 例11.1 (a) (b) (c) (d) (e) 显然：(a)、(b)、(c)、(d)都是树. (e)是林。 (c)是平凡图，称之为平凡树，其结点度数为0。 而在任何非平凡树中，都无度数为0的结点。 * 计算机学院 * 树的性质 定理11.1设T是非平凡图﹙n,m﹚，则以下关于树的命题都是等价的： T连通且无圈； T无圈且m＝n-1； T连通且m＝n-1； T无圈，但在T中任何二结点之间增加一条新边后有且仅有一个圈； T连通的，但删除T中的任意一条边后，便不连通；(n?2) T中每一对结点之间有且仅有一条道路(n?2)。 常用结论 * 计算机学院 * 证明 采用循环论证方法。 即只需证1)?2)?3)?4)?5)?6)?1)即可。 1)?2)用数学归纳法证明，对n作归纳。 当n＝2时，m＝1，显然有m＝n-1； 假设当n＝k时，命题成立； 当n＝k+1时，由于T连通而无圈，所以T中至少有一个度数为1的结点v0. 为什么? 在T中删去v0及其关联的边，便得到k个结点的连通而无圈的图，由归纳假设知它有k-1条边。再将结点v0及其关联的边加回到原来的图中得到原图T。所以T中含有k+1个结点和k条边，为此满足：m＝n-1。 * 计算机学院 * 2)?3) 设T有个分支T1,T2, …,Tk,则由2)知,每支Ti是无圈且连通的(ni,mi)图， 由1)?2)知： mi=ni-1 因此 ∵m=n-1 ∴k=1,即T是连通的 * 计算机学院 * 5)?6)（反证法） 由于T是连通的，因此T中任意二结点vi和vj之间都有道路。 若此道路不唯一，则T中含有回路，删去回路上的一条边，T仍然是连通的，这就与5）矛盾。所以此道路是唯一的。 * 计算机学院 * 推论11.1.1 任意非平凡的树T＝(n，m)中，至少有两片树叶。 证明因树T是连通的，从而T中各结点的度数均大于等于1。设T中有k片树叶，其余结点的度数均大于等于2。于是有 2m＝deg(v1)+deg(v2)+deg(v3)+……+deg(vn)  ?k+2(n-k)＝2n-k。 由于树中有m＝n-1，于是有： 2(n-1)?2n-k， 由此可得：k?2。这就说明T中至少有两片树叶。■ 推论11.1 .2 阶大于2的树必有割点。 * 计算机学院 * 定义11.2　若连通图G的某个生成子图是一棵树，则称该树为G的生成树T。 生成树T中的边称为树枝； G中不在T中的边称为树补边； G-T称为树补。（这是一个边集合） 　　对连通图G＝(n,m)，G的生成树T有n个结点，n-1条边，m-n+1条树补边。 图G＝V1 ,E1和图H＝V2 ,E2。 若V2=V1， E2?E1，则称H是G的生成子图。 * 计算机学院 * 例11.2 在上图中(b)、(c)所示的树T1、T2，它们都是图(a)的生成树，而图(d)所示的树T3，则不是图(a)的生成树。  对于生成树T1，e1,e2,e3,e4是树枝，而e5,e6,e7是树补边，集合{e5,e6,e7}是T1的树补；  对于生成树T2，e1,e2,e6,e7是树枝，而e3,e4,e5是树补边，集合{e3,e4,e5}是T2的树补。 (a) v1 v2 v3 v4 v5 e1 e2 e7 e6 e3 e4 e5 e4 e1 e3 (b) v1 v2 v3 v4 v5 e2 T1 (c) v1 v2 v3 v4 v5 e1 e2 e7 e6 T2 (d) v2 v3 v4 v5 e2 e3 e4 T3 * 计算机学院 * 定理11.2 任意一个无向连通图G都含有生成树。 证明1.若G是无圈，则G本身就是一棵生成树； 2.若G至少存在一个圈，在此圈中删去其中任意一条边得G1，此时不会影响图G的连通性； 3.若G1仍然有圈，再在任意一个圈中删去其中任意一条边得G2，此时仍不会影响图G1的连通性。 4.重复上述步骤，直至得到一个连通图T，且T是无圈的，但T与G有同样的结点集，所以，T是G的生成树。 推论11.2.1 每个n阶连通图，其边数m≥n-1。