离散数学 树ppt课件

第九章常用图,1,9.1.1树及其基本性质,树：不含回路的简单连通无向图。,叶：在树中，次数为1的结点。,分支结点,树枝,4,2,9.1.1树及其基本性质,定理9.1在(n,m)树中必有m=n-1。,连通,不包含回路,树,定理9.3图G是树的充分必要条件是图G的每对结点间只有一条通路。,在T中不相邻接的任意两结点间添加一条边后形成的图有且仅有一个圈,3,9.1.1树及其基本性质,定理9.2具有两个结点以上的树必至少有两片叶。,例114个结点的树：,树是最小连通图，也是最大无回路图。,4,9.1.2有向树,有向树：在有向图中如果不考虑边的方向而构成树。,(a),外向树、内向树,5,9.1.2有向树,图1,外向树:有向树T满足1)T仅有且仅有一个结点它的引入次数为0;2)T的其他结点的引入次数均为1；3)T有一些结点，它的引出次数为0,根树,6,9.1.2有向树,图1,结点的级：由外向树的根到结点的通路长度。,7,9.1.2有向树,例2.用外向树表示家族中的人员关系。,父子关系,8.3二元树,有序树,8,9.1.2有向树,图2,内向树:有向树T满足1)T仅有且仅有一个结点它的引出次数为0;2)T的其他结点的引出次数均为1；3)T有一些结点，它的引入次数为0。,9,9.1.3二元树,m元树：一n个结点的外向树如果满足,例3.,3元树,2元树,3元完全树,2元完全树,m元完全树：如满足(除叶外),10,1)从根开始，保留每个父亲与其最左边儿子的连线，撤消与别的儿子的连线；,9.1.3二元树,有序树转化为二元树的一般步骤：,2)兄弟间用从左向右的有向边连接；,3)左儿子为直接处于给定结点下面的结点；右儿子为处于同一水平线上与给定结点右邻的结点。,11,9.1.3二元树,(b),a,b,d,(c),二元树,省略边的方向,12,9.1.3二元树,v1,v2,v3,v4,v5,v6,v7,v8,v9,v10,v11,(a),v1,13,9.1.3二元树,一个森林转换为二元树的一般步骤：,1)先把森林中的每棵树表示成二元树；,2)除第一棵二元树外，依次将每棵二元树作为左边二元树的根的右子树。,14,9.1.3二元树,a,b,c,d,f,g,j,i,h,e,图1,a,15,9.1.4生成树,生成子图,生成树：若连通图G的生成子图是一棵树。,无向图,16,9.1.4生成树-破圈法,破圈法：,在G中寻找基本回路，找到后在此回路中删除一条边，重复该过程，直至G中无基本回路出现为止。,17,9.1.4生成树-破圈法,a,b,c,d,e,一个连通图可以有很多个生成树。,18,9.1.4生成树-避圈法,避圈法,19,9.1.4生成树-避圈法,练习：,5,20,9.1.4生成树-练习,例设有6个城市，它们间有输油管道连通，为了保卫油管不受破坏，在每段油管间必须派一连士兵看守，为保证正常供应，最少需多少连士兵看守？,21,9.1.4最小生成树,设是一连通的有权图，则G中具有最小权的生成树。,最小生成树,现实意义,22,9.1.4最小生成树,Kruskal算法,要点：在与已选取的边不成圈的边中选取最小者。,构造,23,9.1.4最小生成树,例设有6个城市，它们间有输油管道连通，为了减少消耗，应如何铺设输油管道？,2,1,5,4,2,1,2,2,3,4,4,Kruskal,破圈法,8,24,9.1.4最小生成树,练习：,4,12,10,6,1,5,8,7,11,9,2,3,25,补充：二元树的应用,1.表达式,方法是：将表达式的运算符作为分支结点，将运算量作为叶结点画出二叉树。,26,例1,+,/,-,*,-,/,补充：二元树的应用,27,补充：二元树的应用-练习,练习：,28,补充：二元树的应用,2.前缀码,由0和1的字符串组成的集合叫前缀码，其中集合的每个元素都不是另一元素的前缀（即左子串）。,如集合00,10,11,010,011是前缀码?,00,01,001,29,补充：二元树的应用,给定一棵二元树，对每个分支点引出的左侧的边标记为0，右侧的边标记为1。,0,0,1,1,0,00,010,011,30,补充：二元树的应用,练习：,给出与前缀码00,10,11,010,011对应的二元树。,00,010,011,10,11,31,9.2平面图,印刷电路布线,32,电路布线,a,b,c,1,2,3,33,9.2.1平面图的基本概念,(a),平面图：设无向图,如果能把G的所有结点和边画在平面上，使得任何两条边除公共结点外没有其他的交点。,34,9.2.1平面图的基本概念,当且仅当一个图的每个连通分支都是平面图时，这个图是平面图。,35,9.2.1平面图的基本概念,(a),(c),(e),36,9.2.1平面图的基本概念,无回路的图是平面图。,一种判别平面图的直观方法：,对于有回路的图找出一个长度尽可能大的且边不相交的基本回路。(2)将图中那些相交于非结点的边，适当放置在已选定的基本回路内侧或外侧，若能避免除结点之外边的相交，则该图是平面图；否则，便是非平面图。,37,9.2.1平面图的基本概念,(a),(b),38,9.2.1平面图的基本概念,(b),波兰数学家,库拉托夫斯基(K.Kuratowski),1930,判别平面图充要条件,39,9.2.2平面图的区域,a,b,c,d,e,1,2,3,平面图的区域:平面图中四周为边所包围的最小平面块。,边界：包围区域的回路称为此区域的边界。,区域面积为有限者称为有限区域。,1，2,无限区域,长度称为面的次数,deg(1),40,9.2.2平面图的区域,a,b,d,e,h,c,f,g,1,2,3,4,?区域,1：(a,b,c,a),2:(b,d,e,b),3:(b,c,e,b),4:(a,b,d,e,c,a),一个平面图有一个惟一的无限区域。,41,9.2.2平面图的区域,1750,定理9.4：设图G是一个(n,m)连通平面图，它的区域数为r，则有欧拉公式,归纳法(m),42,9.2.2平面图的区域,定理9.5设图G是一个(n,m)连通平面图，且图G中无环，其边数大于1，则必有,43,9.2.2平面图的区域,3n-6=910=m,2n-4=89=m,定理:若G是每个面由4条或4条以上的边围成的连通平面图，则有,44,9.2.3判别平面图的库拉托夫斯基定理,A,B,C,D,E,a,b,c,d,e,彼得松图,45,9.2.3判别平面图的库拉托夫斯基定理,46,9.2.3判别平面图的库拉托夫斯基定理,库拉托夫斯基定理：,一个图是平面图,它的任何子图都不可能减缩到,47,9.2.3判别平面图的库拉托夫斯基定理,练习：判断下图是否为平面图。,1,2,3,4,5,6,7,8,1,2,3,4,5,6,7,8,8,48,练习：如果无向图G的节点数n11，证明G与G的补图至少有一个不是平面图。,练习：,证明：若G与补图均为平面图，设它们的边数分别为m1和m2.,m13n-633-6=27,m23n-633-6=27,m1+m254,49,练习：,n个结点的无向完全图的边数,根据补图的定义,m1+m2=m,m1+m255,矛盾,50,9.3两步图,二部图,偶图,51,两步图,两步图,互补结点子集,52,两步图,4,定理9.7图G是一个两步图的充分条件是G的所有回路的长度为偶数。,53,两步图-练习,P1609.5已知关于人员a,b,c,d,e,f的下述事实：a说汉语、法语和日语；b