离散数学(Ch12树)

1,第十二章树,树是图论中应用最广泛的子类之一。特别是计算机科学中，树在数据库的数据组织以及数据关联中非常有用。树具有简单的结构,又具有许多重要的性质.,12.1树的一般定义12.2根树与有序树12.3二元树12.4生成树12.5割集,2,12.1树的一般定义,定义12.1如果无向图T连通且无圈,则称T为树.,定理12.1设T是树,则在T的任何两个不同顶点之间有唯一的基本链.若在T两个不邻接的顶点之间加上一条边e,则图T+e仅有一个圈.,连通有链有基本链;唯一性:如果有两条不同的基本链,则必有圈,矛盾;加一条边e,则“基本链”+e构成圈.该圈是仅有的一个圈,如还有圈,则不加e也有圈,矛盾.,3,定理12.2设树T是一个(n,m)图,则m=n-1.,定理12.3在非平凡树T中,至少存在两个度数为1的顶点.,(第二数学归纳法)n=1,n=2时显然成立;假设所有iP1),m(T)m(T)=(Pxlx+P1l1)(P1lx+Pxl1)=(PxP1)(lxl1)0这与T是最优相矛盾.所以lx=l1.,既然lx是最大级,此时可安排兄弟结点,显然应选P2.所以,带权P1和P2的树叶为兄弟,且在最优二元树的最大级.,14,定理12.6设T是带权P1,P2,Pt的最优二元树,并且P1P2Pt,若将带权P1和P2的树叶的父结点改为带权P1+P2的树叶,得到一个新二元树T,则T是带权P1+P2,P3,Pt的最优二元树.,显然m(T)=m(T)+(P1+P2)假设T不是最优,即另有一个带权P1+P2,P3,Pt的最优二元树T”.将T”中带权P1+P2的树叶改为所属的两个子结点P1,P2,得另一树T*,则m(T*)=m(T”)+(P1+P2).,由于T”是最优二元树,故m(T”)m(T),于是可得m(T*)C(x),则与T的选边方法不符,故C(ei+1)=C(x).于是T也是最小生成树,且T与T的公共边比T*与T的公共边多了一条.循环下去,将T看作是新的T*,每次都使公共边多一条,最后完全相同,即得T也是最小生成树.,23,12.5割集,定义12.9设G=为连通无向图,如果G中有边集EE,把E中所有边去掉将使图G分离为两个连通分支,但去掉E中任一真子集,图G仍将连通,则称E为图G的一个割集.,割集:e1,e4,e5,e6,e7,24,割集的另一种说法:对于无向连通图G,把G的顶点分成两个不相交的子集(划分),使每一子集的导出子图是连通的,则将这两个子集中的顶点连接起来的边集,是图的一个割集.,割集与生成树:去掉生成树中任一条树枝(树的割边),即能产生两个顶点子集(这两个子集的导出子图是连通的).所以,生成树TG中的每条树枝再加上求生成树时去掉的各边,即构成图G的一个割集-称为对应于该条树枝的基本割集.这些基本割集即构成基本割集组.,对应于不同的生成树，其对应的基本割集组是不同的。,25,树枝e2,e8,e6,e3对应的基本割集分别是：,D1e1,e5,e2D2e1,e4,e8D3e1,e4,e5,e6,e7D4e3,e4,e7,u1,u2,u3,u4,e1,e2,e5,e7,树枝e1,e2,e5,e7对应的基本割集分别是：,D1e1,e4,e8D2e2,e6,e3D3e3,e4,e5,e6,e8D4e3,e4,e7,26,割集、圈、生成树之间的关系：,定理12.8一个圈和任何生成树的补至少有一条公共边.,定理12.9一个割集和任何生成树至少有一条公共边.,定理12.10任何一个圈和任何一个割集都有偶数条(含0条)公共边.,设有一个圈和某个生成树的补没有共同边，则这个圈应包含在生成树中，但这是与树的定义矛盾的。,设有一个割集和某个生成树没有共同边，那么将这个割集去掉，生成树将被完整得保留下来。也就是说，去掉一个割集后没有将图分离成两个连通分支，这是与割集的定义矛盾的。,27,定理12.11图G的生成树TG,设D=e1,e2,ek是TG的一个基本割集,其中e1是树枝,e2,e3,ek是弦,则e1包含在对应于e2,e3,ek的基本圈里,但e1不包含在任何其它的基本圈里.,证明设C是对应于弦e2的基本圈，注意这时D和C已经有一条共同边e2。根据定理12.10，D和C还应有另一条共同边。因为C中除e2是弦外其他的边均为树枝，所以D和C的另一条共同边应为树枝。但D中只有e1为树枝，所以D和C的另一条共同边只能是e1，这就证明e1了包含在对应于e2的基本圈里。同样可证e1也包含在对应于e3,ek的基本圈里。另一方面，设C是对应于不在D中的弦的基本圈。因为除这条弦外，C中其它的边都是树枝，而D和C就只能有e1为树枝。所以如果e1包含在C中的话，D和C只能有这一条共同边e1，与定理12.10矛盾，从而证得e1不包含在任何其他得基本圈里。,28,定理1