集合论与图论第15讲树

1、树的等价定设G=是n阶m边无向图,定理(1) G是树(树的等价定设G=是n阶m边无向图,定理(1) G是树(连通无回 (2) G中任何2顶点之间有唯一路m=n-m=n-(5G极小连通(6G极大无回唯一 所有边是无增加任何新边产42008-11-定理9.1证明证明(1) G是树(连通无回(2)G中任何2(1)(2): u,vV, G连通, u,v有回路如果u,v之间的路径不唯一!则G52008-11-定理9.1证明证明(1) G是树(连通无回(2)G中任何2(1)(2): u,vV, G连通, u,v有回路如果u,v之间的路径不唯一!则G52008-11-定理9.1证明G中任何2证明(续定理9.

2、1证明G中任何2证明(续(2)(3):任2点之间有唯一路径无圈 (反证: 有圈存在2点,它们之间有2条路径.) m=n-1(归纳法): n=1时,m=0. 设nk时成立,当n=k+1时, 任选1边e, G-e有2个连通分支, m=m1+m2+1=(n1-1)+(n2-1)+1=n1+n2-1n-1.m1=n1-1 m2=n2-12008-11-6定理9.1证明G m=n-G m=n-证明(续(3)(4):G连通定理9.1证明G m=n-G m=n-证明(续(3)(4):G连通假设G有s个连通分支, 则每个连通分支都是树, 所以m1=n1-ms=(n1-1)+(n2-1)+(ns-s=n-所以m

3、2=n2-ms=ns-72008-11-定理9.1证明(5)G定理9.1证明(5)G极小连通证明(续(4)(5):所有边是桥eE,G-e是n阶(n-2)边图, 一定不连通(连通mn- 1), 所以e是割边.em=n-m=n-82008-11-定理9.1证明无圈 增加任何新边得唯G极小连通G极大无回圈所有边是桥无圈证明(续G连通, u,v之间有唯一路径则定理9.1证明无圈 增加任何新边得唯G极小连通G极大无回圈所有边是桥无圈证明(续G连通, u,v之间有唯一路径则(u,v)是唯一的圈92008-11-定理9.1证明无圈 增加任何新边得唯(6) G极大无回圈G是树(连通无回证明(续):(6)(1)

4、: G连通: G(u,v)有唯一的圈C-(u,v)是u,v之间#路径2008-11-定理9.1证明无圈 增加任何新边得唯(6) G极大无回圈G是树(连通无回证明(续):(6)(1): G连通: G(u,v)有唯一的圈C-(u,v)是u,v之间#路径2008-11-定理非平凡树至少有2个树证明设T有定理非平凡树至少有2个树证明设T有x个树叶由定理1和握手定理, 2m = 2(n-1) = 2n-2 = d(v)= v是树叶d(v) + v是分支点x2(n-x2n-x, x22008-11-无向树的计数n(1)阶非同构无向树的个无向树的计数n(1)阶非同构无向树的个tn的生成函数(generati

5、ng t(x)=t1x+t2x2+t3x3+tnxnOtter公式t(x)=r(x)-(r(x)2-r(x2)/r(x)的递推公式r(x)=xi=1(1-xi)-r(x)=r1x+r2x2+r3x3+rnxn2008-11-tn2008-11-nnnn119213142536678tn2008-11-nnnn119213142536678无向树的枚举画出所有非同构的n2008-11-无向树的枚举画出所有非同构的n2008-11-6阶非同构无向n=6:2008-11-6阶非同构无向n=6:2008-11-7阶非同构无向n=7:2008-11-7阶非同构无向n=7:2008-11-8阶非同构无向n

6、=8:2008-11-8阶非同构无向n=8:2008-11-8阶非同构无向树(续n=8:2008-11-8阶非同构无向树(续n=8:2008-11-8阶非同构无向树(解法度数列有11种8阶非同构无向树(解法度数列有11种111111111111122111112311222222008-11-8阶非同构无向树(解法度数列有11种111122311122222008-11-8阶非同构无向树(解法度数列有11种111122311122222008-11-星Sn=K1,n-2008-11-星Sn=K1,n-2008-11-生成树生成树TGV(T)=V(G)T树枝(tree edge): 弦(chor

7、d): eE(G)-余树GE(G)-E(Tn-1m-条-11-生成树生成树TGV(T)=V(G)T树枝(tree edge): 弦(chord): eE(G)-余树GE(G)-E(Tn-1m-条-11-定理无向图G证明显然G有生成() 破圈法#2008-11-定理无向图G证明显然G有生成() 破圈法#2008-11-三个推论和一个定推论1: G是n阶m边无向连通图mn-三个推论和一个定推论1: G是n阶m边无向连通图mn-#推论T是n阶m边无向连通图G的生成 |E(T)|=m-#推论3: T是无向连通图G的生成树, C是G定理设T是连通图G的生成树S是中的割集则ET2008-11-推论 E(

8、T )E( C ).C是G中的圈则证明: (反证若ETE(CE(CE(TT中有回路CT是树!TT2008-11-G推论 E( T )E( C ).C是G中的圈则证明: (反证若ETE(CE(CE(TT中有回路CT是树!TT2008-11-G定理设T是连通图G的生成树则ETS是G中的割集证明: (反证若ETS=TG-S,则G-S连通, S是割集!T2008-11-G定理设T是连通图G的生成树则ETS是G中的割集证明: (反证若ETS=TG-S,则G-S连通, S是割集!T2008-11-G定理设G是连通图T是G的生成树e是T的弦定理设G是连通图T是G的生成树e是T的弦,2008-11-定理9.4

9、证明设设P(u,v)是u与v之间在中的唯一路定理9.4证明设设P(u,v)是u与v之间在中的唯一路径则P(u,v)e是由弦e和其他设e1,e2 是不同的弦,对应的圈是Ce1,Ce2,则e1E(Ce1)-E(Ce2), e2E(Ce2)-E(Ce1), 所以Ce1 Ce22008-11-例9.1(破圈法设G是无向连通图GG,G无圈则G中存在生成树例9.1(破圈法设G是无向连通图GG,G无圈则G中存在生成树T, GTG.证明不妨设G有圈C1(否则G是树则e1E(C1)-令G1=G-则e2E(C2)-若G1还有圈令G2=G1重复进行G-#直到Gk=G-e1,e2,ek无圈为止2008-11-基本(f

10、undamental)设G是n阶m边无向连通图T是G的生成树T=e1,e2,em-Ter中的唯一回路基本回路基本回路系统C1,C2,Cm-圈秩(G)=m-(:C1TT2008-11-G基本(fundamental)设G是n阶m边无向连通图T是G的生成树T=e1,e2,em-Ter中的唯一回路基本回路基本回路系统C1,C2,Cm-圈秩(G)=m-(:C1TT2008-11-G定理设G是连通图, T是G的生成树, e是T的树枝,定理设G是连通图, T是G的生成树, e是T的树枝,则G中存在由树枝e和其他弦组成的割集并2008-11-定理9.5证明: e是T的桥, 设T-e的两个连通定理9.5证明:

11、 e是T的桥, 设T-e的两个连通分支是T1与T2则E(G)(V(T1)&V(T2)是由树枝e和其设e1,e2是不同的树枝,对应的割集Se1,Se2, 则e1Se1-Se2, e2Se2-Se1, 所以 Se2. 2008-11-基本割设G是n阶m边无向连通图T=e1,e2,en-T是G的生成树基本割集er对应的唯一割集基本割集系统S1,S2,Sn-割集秩基本割设G是n阶m边无向连通图T=e1,e2,en-T是G的生成树基本割集er对应的唯一割集基本割集系统S1,S2,Sn-割集秩(G)=n-(:T2008-11-G例G如图,T=a,b,c,e,i是G的生成树,求对应的基本回路系统和基本割集系

12、统abc2008-11-e例G如图,T=a,b,c,e,i是G的生成树,求对应的基本回路系统和基本割集系统abc2008-11-ef例9.2解T=d,f,g,h,基本回路Cf=fcai,Cg=gebai,Ch=heba,基本回路统Cd,Cf,Cg,Ch基本割集例9.2解T=d,f,g,h,基本回路Cf=fcai,Cg=gebai,Ch=heba,基本回路统Cd,Cf,Cg,Ch基本割集Sb=b,d,g,h, Sc=c,d,f, Si=i,g,f, 基本割集系统: #aabcbc2008-11-efef生成树的计数: 标定图G的生成树的个T1T2:G-e: 删除Ge:收缩生成树的计数: 标定图G

13、的生成树的个T1T2:G-e: 删除Ge:收缩2008-11-定理e非环(G)=(G-e)+定理e非环(G)=(G-e)+2008-11-定理6证明: e非环不含e的G的生成树个数: (G-定理6证明: e非环不含e的G的生成树个数: (G-(2) 含e的G的生成树个数: #2008-11-例= + + = 0 += 1 + = 1 + 1+ = 1 + 1 +1 + 1 =2008-11-#例= + + = 0 += 1 + = 1 + 1+ = 1 + 1 +1 + 1 =2008-11-#定理Cayley公式:n2 (Kn)=nn-定理Cayley公式:n2 (Kn)=nn-证明: 令V

14、(Kn)=1,2,n, 用V中元素构造长度为)的序列,有个不同序列,这些序列与K的生成树是一一对应的.2008-11-定理9.7证明(续): (1) 由树构造序列设T是定理9.7证明(续): (1) 由树构造序列设T是任意生成树令k1=min r | dT( r )=1 , NT(k1)= l1 , k2=minr|dT-k1(r)=1,NT-k1(k2)=l2,kn-2=minr|dT-k1,k2,kn-3(r)=1NT-k1 ,k2,kn-3(kn-2)=ln-得到序(l1, l2, ln-2008-11-定理9.7证明举3646464555888877776466552008-11-定理

15、9.7证明举3646464555888877776466552008-11-定理9.7证明(续): (2) 由序列构造树令设(定理9.7证明(续): (2) 由序列构造树令设(l1, l2, ln-2)是任意序列k1=minr|rV-l1,l2,ln-2k2=minr|rV-k1,l2,ln-2kn-2=minr|rV-k1,k2,kn-3,ln-2ln-1=minr|rV-k1,k2,kn-3,kn-2,kn-1 E(T)=(ki,li)|i=1,2,n-2008-11-定理9.7证明举定理9.7证明举l7=min(V-2008-11-定理9.7证明举18273645定理9.7证明举182736452008-11-定理9.7可以证明上述