[理学]离散数学课件 7.pptVIP

Ma Qianli,South China Univ.of Tech. 6-2 树 6-2-1 树的定义 定义: 一个连通且无回路的图称为树. 树叶(悬挂点):度数为1的顶点. 分支点(内点):度数大于1的顶点. 树的几个等价定义 定理：对于给定图T, 无回路的连通图. 无回路且e=n-1,其中e是边数,n是顶点数. 连通且e=n-1. 无回路,但增加任一新边,得到一条且仅一条回路(这时T也称为最大无回路图),n?3 连通但删去任一边后,便不连通(这时T称为最小连通图). 在每一对顶点之间有唯一的一条路. 推论 如果G是n个顶点,w个分支的森林,则G有n-w条边. 证明: 设每个分支的顶点数为:n1,n2,…nw. n1+n2+…+nw=n 每个分支的边数为: n1-1,n2-1,…nw-1. 所以总边数为: n1-1+n2-1+…+nw-1 =n-w 定理 在任一棵数T中,至少有两片数叶(n?2). 证明： 由于T是连通的，对任vi?T，d(vi)?1,且? d(vi)=2(n-1),如果T中至多有一个顶点度数为 1,其他顶点的度数均大于等于2,于是? d(vi) ? 2(n-1)+1,导致矛盾.所以T中至少有两个顶点度数为1. 6-2-2 生成树和割集 生成树 定义: 给定连通图G,如果它的生成子图T是树,则称T为G的生成树.T中的边称为树枝(或枝), 在G中而不在T中的边称为T的弦. 定理 定理：任何连通图G至少存在一棵生成树。（G是连通图当且仅当G有生成树。） 证 用破圈法. 若图中无圈, 则图本身就是自己的生成树. 否则删去圈上的任一条边, 不破坏连通性, 重复进行直到无圈为止, 得到图的一棵生成树. 推论：连通图G有n个顶点，e条边，则e?n-1。 定义 如果图G有n个顶点，e条边，w个分支，则n?w，e ? n -w。定义n-w为图G的秩(各分支的生成树的枝数之和),e-n+w为图G的零度(弦数，即余树的支数之和). 边割 边割:如果图G=(V,E)中顶点集V划分为P和P两部分互补的顶点集, (P?V???P=V-P),图G中一端在P中,另一端在P中的所有边的集合,称为G的边割. 例 基本回路与基本回路系统 基本割集 给定连通图G的生成树T,称仅包含T中一条枝的割集为关于T的基本割集. 基本割集与基本割集系统 注意： 基本回路（只含一条弦，其余边为树枝） 基本割集（只含一条树枝，其余边为弦） 回路和割集的性质 定理1 任何一条回路和任何生成树的余树至少有一条公共边。 证明：如果一条回路和一棵生成树的余树没有公共边，则这个回路包含在生成树中，是不可能的。 回路和割集的性质 定理2 任何一个割集和任何生成树至少有一条公共边。 证明：如果割集和生成树没有公共边，删去该割集后留下一棵完整的生成树，也就是说，删去一个割集后，不能将图G分为两个分支，与割集的定义相矛盾。 最小生成树 设无向连通带权图G=(V,E,W)，T是G的一棵生成树，T各边带权之和称为T的权，记作W(T)。G的所有生成树中带权最小的生成树称为最小生成树。 Kruskal算法 (避圈法)： 将n阶无向连通带权图的边按权值从小到大的顺序排列，取权值最小的边作为T的一边，然后按权从小到大逐次取出一条边检查，每取出一条边，只要保持没有回路，就将该边加入T中，把所有边检查完便得到一棵生成树。 避圈法 (Kruskal) (1) 将所有非环边按权从小到大排列, 设为e1, e2, …, em (2) 令T = ? (3) For k=1 to m Do 若ek与T 中的边不构成回路, 则将ek加入T 中 实例 求图的一棵最小生成树 m元树 m元（叉）树： 在根树中，如果每个顶点的出度小于或等于m，则称这棵树为m元树。 二元（叉）树: m=2时称为二元树. 完全m元树： 在根树中，如果每个顶点的出度等于m或零，则称这棵树为完全m元树。 完全正则m元树： 所有树叶级数相同的完全m元数称为完全正则m元树.　　　　 定理 若完全二叉树T有n个分支点，且所有分支点的路长度总和为I，所有树叶的路长度总和为E，则E= I +2n。 二元树 下图所示的3棵树，都是带权1，3，4，5，6的2元树。 前缀符号法或波兰符号法 在②式中，可将全部括号去掉： 　　　 ? + ? + a ? b c d e ? f g ④ 在④中规定，每个运算符与它后面紧邻的两数进行计算，其计算结果是正确的。在此种算法中，因为运算符在参加运算的两数的前面，因而称为前缀符号法或波兰符号法。 后缀符号法或逆波兰符号法 　　在③式中，也可将全部括号去掉： 　　　a b c ? + d ?e