《离散数学课件资料》PPT课件

《《离散数学课件资料》PPT课件》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第九章树§9.1无向树及生成树§9.2根树及其应用7/14/20211离散数学树：连通而不含回路的无向图称为无向树，简称树。常记做T。树叶：树中度数为1的结点。分支点：树中度数大于1的结点。森林：连通分支数大于等于2,且每个连通分支都是树的无向图。§9.1无向树及生成图平凡树：平凡图。本章所指回路为简单回路或初级回路7/14/20212离散数学7/14/20213离散数学一、无向树(1)G连通且不含回路；(2)G中无回路，且m=n-1，其中m为边，n为结点数；(3)G是连通的，且m=n-1;(4)G中无回路，但在G中任意不相邻两结点之间增加一条边，就得到唯一的一条初级回路；(5)G是连通

2、的且G中每条边都是桥；(6)G中每一对结点之间有唯一的一条基本通路。树的等价定义任意非平凡树T(n,m)至少有两片树叶。定理设T有k片树叶，于是2mk+2(n-k)，则2(n-1)2n-k，则k27/14/20214离散数学例：画出6阶所有非同构的无向树。(1)1，1，1，1，1，5(2)1，1，1，1，2，4(3)1，1，1，1，3，3(4)1，1，1，2，2，3–两种(5)1，1，2，2，2，2解：设T是6阶无向树，T的边数m＝5，由握手定理可知，∑d(v)＝10，且δ(T)≥1，△(T)≤5。故T的度数列必为以下情况之一：一、无向树7/14/20215离散数学7/14/202

3、16离散数学二、生成树生成树：若连通图G的某个生成子图是一棵树，则称该树为G的生成树，记做TG。树枝：生成树TG的边。弦：G中不在TG中的边。生成树的余树(补)：TG的所有弦的集合的导出子图。余树不一定是树,也不一定连通。7/14/20217离散数学二、生成树dbaecdbaecbaec图G生成树TG生成树TG的补无向连通图如果本身不是树，它的生成树是不唯一的，但所有连通图都具有生成树。7/14/20218离散数学推论1:G为n阶m条边的无向连通图，则m≥n1。(要把n个顶点联系起来至少需要n-1条边)推论2:设G是n阶m条边的无向连通图，T为G的生成树，则T的余树中含有m-n+1条边

4、（即T有m-n+1条弦）。定理任何连通图G至少存在一棵生成树。二、生成树7/14/20219离散数学基本回路:设T是n阶m条边的无向连通图G的一棵生成树，设e1,e2,…,emn+1为T的弦。设Cr为T添加弦er产生的G的回路,该回路只含生成树T的一条弦er，其余边均为树枝，称Cr为对应T的弦er的基本回路，r＝1,2,…,mn+1。aedbfc二、生成树基本回路系统：{C1,C2,…,Cmn+1}为G对应T的基本回路系统。一个连通图对应不同的生成树的基本回路及基本回路系统可能不同，但是基本回路的个数相等，等于mn+1。7/14/202110离散数学三、最小生成树最小生成树：设G

5、=是无向连通带权图，T是G的一棵生成树，T各边带权之和称为T的权，记为W(T)。G的所有生成树中带权最小的生成树称为G的最小生成树。Kruskal算法(避圈法)：设n阶无向连通带权图G有m条边，它们带的权分别为，设。（1）取e1在T中（ei非环，若是环，则放弃）（2）若e2不与e1构成回路，取e2在T中，否则放弃e2，考查e3，继续这一过程，直到形成生成树T为止。7/14/202111离散数学abcdegf195141827168213ae12dcbgf7148531621Kruskal算法:71218197/14/202112离散数学§9.2根树及其应用其中：入度为0的顶

6、点称为树根，有向树：一个有向图，若略去所有有向边的方向后得到的无向图是一棵树，则称该有向图为有向树。根树：非平凡的有向树，若恰有一个结点的入度为0，其余所有顶点的入度均为1，则称此有向树为根树。入度为1，出度为0的顶点称为树叶，入度为1出度大于0的顶点称为内点，内点和树根统称为分支点。7/14/202113离散数学一、有向树层数:从树根到任意顶点v的通路长度，称为v的层数，记为l(v).树高:层数最大的顶点的层数，记为h(T)。（本书树根为第0层。）v0v1v2v3v4v5v6v7v8v9v10v11v127/14/202114离散数学根树可看成是家族树：(1)若从a到b可达，则称a是b

7、的祖先，b是a的后代；(2)若是根树中的有向边，则称a是b的父亲，b是a的儿子；(3)若b、c同为a的儿子，则称b、c为兄弟。一、有向树根子树：根树T中，任一不为树根的顶点v及其所有后代导出的子图,称为T的以v为根的子树。7/14/202115离散数学二、有序树r元树：每个分支点至多有r个儿子；r元有序树：r元树是有序的；r元正则树：每个分支点恰有r个儿子；r元正则有序树：r元正则树是有序的；r元完全正则树：树叶层数均为树