09离散数学课件资料.ppt

第九章树§§:连通而不含回路的无向图称为无向树,简称树。常记做T。树叶:树中度数为1的结点。分支点:树中度数大于1的结点。森林:连通分支数大于等于2,且每个连通分支都是树的无向图。§:平凡图。本章所指回路为简单回路或初级回路2019/11/152离散数学Date3离散数学一、无向树(1)G连通且不含回路;(2)G中无回路,且m=n-1,其中m为边,n为结点数;(3)G是连通的,且m=n-1;(4)G中无回路,但在G中任意不相邻两结点之间增加一条边,就得到唯一的一条初级回路;(5)G是连通的且G中每条边都是桥;(6)G中每一对结点之间有唯一的一条基本通路。树的等价定义任意非平凡树T(n,m)至少有两片树叶。定理设T有k片树叶,于是2mk+2(n-k),则2(n-1)2n-k,则k22019/11/154离散数学例:画出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的度数列必为以下情况之一:一、无向树Date5离散数学Date6离散数学二、生成树生成树:若连通图G的某个生成子图是一棵树,则称该树为G的生成树,记做TG。树枝:生成树TG的边。弦:G中不在TG中的边。生成树的余树(补):TG的所有弦的集合的导出子图。余树不一定是树,也不一定连通。2019/11/157离散数学二、生成树dbaecdbaecbaec图G生成树TG生成树TG的补无向连通图如果本身不是树,它的生成树是不唯一的,但所有连通图都具有生成树。2019/11/158离散数学推论1 :G为n阶m条边的无向连通图,则m≥n1。(要把n个顶点联系起来至少需要n-1条边)推论2:设G是n阶m条边的无向连通图,T为G的生成树,则T的余树中含有m-n+1条边(即T有m-n+1条弦)。定理任何连通图G至少存在一棵生成树。二、生成树Date9离散数学基本回路:设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。Date10离散数学