课件代数结构第十一章

1、离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院1离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院2离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院3Tree凯莱( Arthur Cayley)(1821-1895)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院4主要内容主要内容 离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院51 树及其性质树及其性质树树（Tree）:无环的连通图无环的连通图森林森林（Forest）平凡树平凡树（Trivial Tree）树叶树叶（Leaf），），外部结点外部结点 (度数为度数

2、为1)分支结点分支结点（Branched Vertex），），内部结点内部结点（除树叶结点之外的结点）（除树叶结点之外的结点）离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院6离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院71 树及其性质树及其性质性质性质设图设图G=（n,m），如果），如果G满足如下三个属性中的两个，则满足如下三个属性中的两个，则G就是一棵树，就是一棵树，且可以推导出另一个属性：且可以推导出另一个属性：1) G连通；连通； 2) G中不存在环；中不存在环； 3) m=n-1离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院81

3、树及其性质树及其性质思考思考 下列命题是否为真？下列命题是否为真？1)在树在树T的任意二结点间添加一条边后，将构成包含该二结点的闭通的任意二结点间添加一条边后，将构成包含该二结点的闭通路，即存在环路，即存在环2)删除树删除树T的任意一条边后，的任意一条边后，T就不连通，即树就不连通，即树T的每一条边均为的每一条边均为T的的割边割边3)树树T的每一对结点间存在惟一一条路径的每一对结点间存在惟一一条路径4)结点数大于等于结点数大于等于2的任意树，至少有两片树叶的任意树，至少有两片树叶5)图图G为为n个结点、个结点、w个分图的森林，则个分图的森林，则G边数为边数为n-w离散数学离散数学 中国地质大学

4、中国地质大学 计算机学院计算机学院91 树及其性质树及其性质 示例示例 树树T具有具有ni个度数为个度数为i的结点，的结点，i=2，3，,k,其余为叶子结其余为叶子结点，问该树有多少叶子结点？点，问该树有多少叶子结点？离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院10相关知识点的回顾 无向图G的生成子图设G =,G =是两个图.若G G且 V V,则称 G 是G的生成子图.离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院112 生成树生成树(Spanning Tree)什么是生成树? 若无向图若无向图G的一个生成子图的一个生成子图T是树，则称是树，则称T为为G

5、的的生成树生成树 树枝树枝、弦弦定理定理11.2 G是连通图当且仅当是连通图当且仅当G中存在生成树。中存在生成树。 请你思考请你思考 1) 只有连通图才有生成树? 2) 连通图的至少有一棵生成树？ 3) 设G为连通无向图，那么G的任一回路与G T(任一生成树T的相对G的补)至少有一条公共边。生成树的构造方法？生成树的构造方法？ “破圈破圈”法法离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院122 生成树生成树(Spanning Tree)求解生成树算法(1)DFS算法 (2) BFS算法213214321543216543217654321876543217654321197

6、65432176543212132143215432165432111栈栈(stack)、队列队列(queue)教材示例教材示例11.2123478956离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院13生成树生成树(Spanning Tree)Cayley定理：n个顶点的标号完全图Kn有nn-2棵生成树(难点) 一个连通图的生成树不唯一。那么一个有一个连通图的生成树不唯一。那么一个有n个个顶点的标号完全图顶点的标号完全图Kn有多少棵生成树有多少棵生成树寻找一个与之同构的数学模型寻找一个与之同构的数学模型由由n个元素构成的长为个元素构成的长为n-2的序列与之同构。的序列与之同

7、构。下面建立序列集合下面建立序列集合(t1,t2,tn-2)与生成树集合之间的双射关系。与生成树集合之间的双射关系。离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院142 生成树生成树(Spanning Tree)由一棵生成树可以得到一个与之对应的序列。12845367(8，3，4，3，8，4)(1，2，5，6，3，7)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院15生成树生成树(Spanning Tree)Cayley定理：n个顶点的标号完全图Kn有nn-2棵生成树12845367(1)(8)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院

8、16Cayley定理：n个顶点的标号完全图Kn有nn-2棵生成树2845367(1，2)(8，3)生成树生成树(Spanning Tree)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院17 生成树生成树(Spanning Tree)Cayley定理：n个顶点的标号完全图Kn有nn-2棵生成树845367(1，2，5)(8，3，4)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院18 生成树生成树(Spanning Tree)Cayley定理：n个顶点的标号完全图Kn有nn-2棵生成树84367(1，2，5，6)(8，3，4，3)离散数学离散数学 中国地质大学

9、中国地质大学 计算机学院计算机学院19生成树生成树(Spanning Tree)Cayley定理：n个顶点的标号完全图Kn有nn-2棵生成树8437(1，2，5，6，3)(8，3，4，3，8)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院20生成树生成树(Spanning Tree)Cayley定理：n个顶点的标号完全图Kn有nn-2棵生成树847(1，2，5，6，3，7)(8，3，4，3，8，4)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院21生成树生成树(Spanning Tree)Cayley定理：n个顶点的标号完全图Kn有nn-2棵生成树84(1，

10、2，5，6，3，7)(8，3，4，3，8，4)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院22生成树生成树(Spanning Tree)(3，2，2，3，4，1)(5，6，7，2，3，4)51326487反之，任给定由结点集合反之，任给定由结点集合V中的元素构成的长为中的元素构成的长为n-2的一个的一个序列序列(t1,t2,tn-2) ，可以如下地画一棵生成树。，可以如下地画一棵生成树。离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院23生成树生成树(Spanning Tree)(3，2，2，3，4，1)(5)V=1,2,3,4,5,6,7,8 V- t1,

11、t2,t6 =5, 6,7,853离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院24生成树生成树(Spanning Tree)(3，2，2，3，4，1)S:(5)V=1,2,3,4,5,6,7,8 V- S-t2,t6 =6,7,8532S:(5，6)6离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院25生成树生成树(Spanning Tree)(3，2，2，3，4，1)S:(5，6)V=1,2,3,4,5,6,7,8 V- S-t3,t6 =7,8532S:(5，6，7)67离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院26生成树生成树(S

12、panning Tree)(3，2，2，3，4，1)S:(5，6，7)V=1,2,3,4,5,6,7,8 V- S-t4,t6 =2,8532S:(5，6，7，2)67离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院27生成树生成树(Spanning Tree)(3，2，2，3，4，1)S:(5，6，7，2)V=1,2,3,4,5,6,7,8 V- S-t5,t6 =3,8532S:(5，6，7，2，3)674离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院28生成树生成树(Spanning Tree)(3，2，2，3，4，1)S:(5，6，7，2，3)V=1,

13、2,3,4,5,6,7,8 V- S-t6 =4，8532S:(5，6，7，2，3，4)6741离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院29生成树生成树(Spanning Tree)(3，2，2，3，4，1)V=1,2,3,4,5,6,7,8 V- S=1，853S:(5，6，7，2，3，4)267418因此，序列集合因此，序列集合t1,t2,tn与与Kn的生成树集合存在双射关系。的生成树集合存在双射关系。离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院302 生成树生成树(Spanning Tree)最小生成树(minimum spanning tre

14、e) 算法？ Kruskal算法算法证明？1 6 2 11 3 7 84 52 3 1 3 3 29 10 1 2 离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院312 生成树生成树(Spanning Tree)算法正确性证明算法正确性证明设设T不是最小生成树，则存在另一棵树不是最小生成树，则存在另一棵树T*，为最小生成树。，为最小生成树。下面证明下面证明T*=T。首先设。首先设T的所有边升序序列为的所有边升序序列为e1e2e3em(对对T而言边的升序序列即是按而言边的升序序列即是按kruskal算法选择边算法选择边的顺序的顺序)：可以证明可以将可以证明可以将e1加入加入T*

15、中得到生成树中得到生成树T1,且满足条件且满足条件w(T1)=w(T*):将将e1加入加入T*中将形成环，此环中必然然存在边中将形成环，此环中必然然存在边e1在在T*中而不在中而不在T中中,于是于是,删除删除e1，则得到生成树，则得到生成树T1，按，按kruskal算法选择边的顺序知算法选择边的顺序知w(e1)=w(e1)，从而，从而w(T1)=w(T*)。依此进行依此进行，可以将，可以将ek加入到加入到Tk-1中，将形成环，此环中必然然存在边中，将形成环，此环中必然然存在边ek在在T*中而不在中而不在T中，于是，删除中，于是，删除ek，则得到生成树则得到生成树Tk。而显然，两边序列。而显然，

16、两边序列e1e2e3ek 与与 e1e2e3ek均不构成环，而按均不构成环，而按kruskal算法，必然有算法，必然有 w(ek)=w(ek)，从而从而 w(Tk)= w(Tk-1)=w(T*) ，最后可以将最后可以将em加入到加入到Tm-1中，得到生成树中，得到生成树Tm，且，且w(Tm)=w(Tk)= w(Tk-1)= =w(T1)=w(T*)。而此时，而此时， T所有边都加入到所有边都加入到Tm中，即中，即Tm=T。故。故w(T)=w(T*)因此，因此，T为最小生成树。为最小生成树。离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院323 有序树有序树(Order tree

17、)有关术语 有向树 根树, 树高度 有序树: (完全)m分树、 (完全)二叉树 父结点父结点/孩子结点；孩子结点； 分支结点分支结点/叶子结点叶子结点, 内部结点内部结点/外部结点；外部结点；孩子结点孩子结点/非孩子结点非孩子结点v v1 1v v8 8v v4 4v v3 3 v v7 7v v6 6 v v2 2 v v5 5离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院333 有序树有序树(Order tree) 若若T T是一棵根树。存在一个从是一棵根树。存在一个从T T的边集的边集E E到自然数集到自然数集N N的映射的映射f f，当，当f(uf(u，v)=nv)=

18、n时，称时，称v v是是u u的第的第n n个个后继后继，并称，并称T T为一棵为一棵有序树有序树。 若有序树若有序树T T的每一结点的每一结点u u，degdeg+ +(u)m(u)m时，对任一边时，对任一边x x，有有f(x)mf(x)m，则称，则称T T为为m m分树分树； 若若m m分树中每一结点分树中每一结点u u，有，有degdeg+ +(u)=m(u)=m或或degdeg+ +(u)=0(u)=0，则，则T T称为称为完全完全m m分树分树( (完全完全m m叉树叉树) )； 若完全若完全m m分树分树T T的所有叶结点到根的距离相等，则称的所有叶结点到根的距离相等，则称T T为

19、为正则正则m m分树分树。离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院343 有序树有序树(Order tree) 例11.6 证明：存在一棵有n片叶的完全两分树。 证明 用数学归纳法：当n=1时，是平凡树，结论是显见。 设n=k-1时，存在完全两分树Tk-1，Tk-1有k-1片叶子。 取Tk-1中任意一片叶子v，加上两个点u、w作为v的后继，得到树Tk，Tk仍是完全两分树，Tk恰好有k片叶。综上命题得证。 离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院353 有序树有序树(Order tree)定理11.5 证明 对i施归纳法：当i=0，1时，结论显见。

20、 设i=k时，(m-1)k=t-1成立。 考虑i=k+1时，设T是具有k+1个分枝点，t片叶的完全m分树。从T中找到一个具有m片叶的分枝点v，去掉v的m片叶，得到树T。T仍是一个m分树，且具有t-(m-1)片叶，k个分枝点。由归纳假设，对于T有：(m-1)k=(t-(m-1)-1，即有(m-1)(k+1)=t-1，亦即对于i=k+1时，结论仍成立。 由归纳原理，定理得证。 离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院363 有序树有序树(Order tree)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院373 有序树有序树(Order tree)问题探讨

21、(1)若T是有n个结点的完全二分树，则T有(n+1)/2片树叶。(2)T为有t片叶的完全两分树，则T有2(t-1)条边离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院383 有序树有序树(Order tree)应用（1）二叉树，树的遍历，逆波兰式（2）前缀码最优二分树Huffman算法求带权为2,3,5,7,8,9的最优二分树离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院393 有序树有序树(Order tree)应用 二叉查找树 决策树， 平衡树 离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院403 有序树有序树(Order tree) 有

22、8枚硬币，其中恰有1枚是假币，假币比真币轻。试用一架天平称出假币，使称量的次数尽可能地少。 11，2 2，3 63 6，7 7，88 左盘轻左盘轻 水平水平 右盘轻右盘轻 1 3 4 5 6 81 3 4 5 6 8 左盘轻左盘轻 水平水平 右盘轻右盘轻 左盘轻左盘轻 右盘轻右盘轻 左盘轻左盘轻 水平水平 右盘轻右盘轻1 2 3 4 5 6 7 8决策树决策树离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院413 有序树有序树(Order tree)应用平衡树：若一棵高度为h的m元树的所有结点都在h或h-1层。1 高度为h的m元树：树叶数t= ,若m元树为完全的平衡的，则h=

23、.离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院42小结与作业小结小结作业作业离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院4311.2平面图与图的着色离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院441平面图的概念离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院451什么是平面图 示例示例4 4平面图的应用平面图的应用：要在三座房屋和三个设施（水、电、气）之：要在三座房屋和三个设施（水、电、气）之间建立管线链接，问是否可能使这些线路互不相交？这个问间建立管线链接，问是否可能使这些线路互不相交？这个问题其实是判断题其实是判断

24、K3,3是否为平面图的问题。是否为平面图的问题。离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院46平面图平面图 G(6，9，5)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院471什么是平面图 示例示例1 1 离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院48什么是平面图 示例示例2 2 (a) (b)离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院49示例3 离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院501什么是平面图 示例示例4 4K3,3是边数最少的非平面图，是边数最少的非平面图，K5是结点数最少

25、的非平面图。是结点数最少的非平面图。离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院512平面图性质1 定理1：一个有限平面图，面的次数之和等于其边数 的两倍。离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院522平面图性质欧拉定理的证明：欧拉定理的证明：证明：证明： 对面数对面数f进行归纳。进行归纳。当当f=1时，时，G中无回路，因而中无回路，因而G是一课树，故有是一课树，故有n=m+1，即，即。假设假设f=k-1时，定理成立。时，定理成立。考察考察f=k时，设图时，设图G有有n个结点，个结点，m条边。因为条边。因为k=2，所以，所以G这至少有一个环将这至少有

26、一个环将外部面与内部面分开。外部面与内部面分开。从任一环中去掉一条边，得到从任一环中去掉一条边，得到G(G仍连通仍连通)，因为去掉的边在还中，一定是两，因为去掉的边在还中，一定是两个面的公共边。将其去掉后这两个面就连成了一个面，图个面的公共边。将其去掉后这两个面就连成了一个面，图G的面数为的面数为k-1，边数为边数为m-1，结点数为，结点数为n。由归纳假设，对图。由归纳假设，对图G n-(m-1)+(k-1)=2 即即。即即f=k时，定理成立。由归纳法得欧拉定理成立。时，定理成立。由归纳法得欧拉定理成立。离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院532平面图性质离散数学离

27、散数学 中国地质大学中国地质大学 计算机学院计算机学院542平面图性质离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院553平面图的判定 如下图所示，G1、G2均为G的细分，当然也可以认为G也是自身的细分。 离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院563平面图的判定 平面图的判定定理：图G是平面图，当且仅当K5与K3,3的任何细分图都不是G的子图。 Peterson图离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院574四色定理 四色猜想四色定理 离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院585着色问题离散数学离散数

28、学 中国地质大学中国地质大学 计算机学院计算机学院598图的着色离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院608图的着色离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院618图的着色 至今还没有一个简单方法可以确定任一图G是否是k色的。通常可用Powell方法对图进行着色，其过程如下： 将图G的结点按度数递减的次序排列(这种排列不一定惟一)。 用第一种颜色对第一点着色，并按排列次序，对与前面着色点不邻接的每一点着上同样的颜色。 用第二种颜色对尚未着色的点重复(2)，用第三种颜色继续这种做法，直到所有的点全部着上色为止。 离散数学离散数学 中国地质大学中国地

29、质大学 计算机学院计算机学院628图的着色v v1 1v v4 4v v2 2v v3 3v v6 6v v8 8v v5 5v v7 7 解 (1) 根据递减顺序排列各结点： v5，v3，v7，v1，v2，v4，v6，v8。 (2) 对第一个点v5着第一种颜色，并对与之不相邻的点v1着第一种颜色。 (3) 对v3着第二种颜色，并对与之不相邻的点v4，v8着第二种颜色。 (4) 对v7和与之不相邻的点v2，v6着第三种颜色。因此，右图是三色图。 离散数学离散数学 中国地质大学中国地质大学 计算机学院计算机学院638图的着色教授教授所授课程所授课程AgnesiAgnesi132,136,211132,136,211BernoulliBernoulli127,131,153127,131,153CauchyCauchy131,132,211131,132,211DescartesDescartes127,131,205127,131,205EulerEuler131,138,154131,138,154FrobeniusFrobenius132,136,201132,136,201GaussGauss127,131,138127,131,138HamiltonHamilton153,154,205153,154,205离散数学