离散数学(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时显然成立;假设所有in的树(i,mi)成立,对(n,m)树T,拆去其一条边,得两棵树:m1=n1-1,m2=n2-1,两边求和得(m1+m2)=(n1+n2)-2,即m-1=n-2,满足m=n-1.设T为(n,m)图,顶点集V={u1,u2,…,un},则∑d(ui)=2m=2n-2.因树T连通,d(ui)≥1.•若所有顶点度数≥2,则∑d(ui)≥2n;•若仅一个顶点度数为1,其它≥2,则∑d(ui)≥2(n-1)+1;所以,至少有两个顶点的度数为1.度数为1的顶点称为“树叶”,度数大于1的顶点称为“分支”4定理12.4设T是非平凡(n,m)无向图,则以下五项等价:⑴T是树;⑵T连通且无圈;⑶T的每一对顶点之间有唯一的一条基本链;⑷T连通且m=n-1;⑸T无圈且m=n-1.⑴⑵由定义⑵⑶由定理⑶⑵有则连通,唯一则无圈⑵⑷由定理⑷⑵假设有圈,该圈含p点p边,则余下n-p点,每点至少需一条边搭上这个圈才能连通,于是边数m≥p+(n-p),矛盾.⑵⑸由定理⑸⑵假设不连通:T1,T2,…,Tk连通分支,各分支连通且无圈,满足mi=ni-1,两边求和得m=n-kn-1,矛盾.5§12.2根树和有序树术语有向树---有向图中不考虑弧的方向时若是一个树.弱连通无半回路6定义12.2若一个有向树有一个引入次数为0的顶点,而所有其它顶点的引入次数都为1,则称其为根树.称引入次数为0的顶点为根.(至少有一个根顶点)定义12.3在根树中,称引出次数为0的顶点为树叶,其它为分支顶点.任何顶点的级,是从树根出发到该顶点的通路的长度.自然树0123倒置树目录7定义12.4若根树的顶点或弧都已指定次序,则称其为有序树.u0u1u2u3u4u5u6u7u8借用家族谱系中的术语来描述根树中的顶点:•从顶点ui出发可达的每个顶点,称其为ui的后裔,而称ui为其后裔的祖先;•从ui出发经一条弧可达的顶点,称其为ui的儿子,而称ui为其儿子的父亲,有同一个父亲的顶点互称为兄弟.8§12.3二元树定义12.5若根树中每一个顶点的引出次数≤m,则称其为m元树.若根树中每个顶点的引出次数都等于m或者0,则称其为完全m元树.在m元树中,若任何顶点的m(或少于m)个子结点分别有m个位置,则称其为位置m元树.二元树完全二元树9位置二元树,又称“二叉树”,每个顶点的两个子结点的位置区分为“左”和“右”.前缀编码---由{0,1}构成的字串标记顶点:⑴树根对应空串;⑵若顶点u的字串为a,则u的左儿子的字串为‘a0’,u的右儿子的字串为‘a1’.01001011位置二元树(前缀编码)01011011不同的位置二元树10位置二元树有序树/树林12345678910树林12345678910父长子---左子树,兄弟---右子树12563478910位置二元树表示的树林11最优二元树---编码中的应用位置二元树的前缀编码可以在通讯中无岐义地表示信息:1001101011bacabc0a110b11c考虑到整体效率---希望使用频繁的字/字母编码短.(长途电话的区号编码)以英文通信为例:26个字母,各字母的使用频率为Pi,编码长度为li,为使表示信息的整个编码串尽可能的短,则∑Pi·li应取最小值.i=1n12带权树:设位置二元树T,有t片树叶对应前缀编码.每片树叶上附加权值Pi(可表示其使用频率等).每片树叶的级li(=前缀编码的码长).称和数m(T)=∑Pi·li为带权树T的权.i=1t定义12.6使权m(T)取最小值的带权二元树,称为最优二元树.(也称Huffman树)13定理12.5设T是带权P1,P2,…,Pt的最优二元树,并且P1≤P2≤…≤Pt,则可使带权P1和P2的树叶为兄弟.设Px树叶有最大级为lx.⑴先证明lx=l1,(即最大级安排给权值最小者.)用反证法.假设lxl1.因lx≥l1,故只可能lxl1.(此时应有PxP1)P1,l1Px,lx(最大级)TPx,l1P1,lx(最大级)T’m(T)–m(T’)=(Pxlx+P1l1)–(P1lx+Pxl1)=(Px–P1)(lx–l1)0这与T是最优相矛盾.所以lx=l1.⑵既然lx是最大级,此时可安排兄弟结点,显然应选P2.所以,带权P1和P2的树叶为兄弟,且在最优二元树的最大级.14定理12.6设T是带权P1,P2,…,Pt的最优二元树,并且P1≤P2≤…≤Pt,若将带权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).P1P2TP1+P2T’由于T”是最优二元树,故m(T”)m(T’),于是可得m(T*)m(T),这与T是最优矛盾.15Huffman算法步骤:34561234561273456127113456127111834561271118301634561271118303456107111728如果将权12改为10：17一个霍夫曼码最容易用一个根树来定义。为了对一个二进制串进行解码，我们从根结点开始沿树向下移动，直到遇到一个字符。1TS0100011ROA01010111我们先从根开始。由于第一位是0，则第一步向右移，接下来向左移然后再右移。在该点遇到第一个字符R、、、最终得到位串代表的单词是RAT。18§12.4生成树定义12.7如果无向图G的一个生成子图T是树,则称T是图G的一个生成树.GG的树G的生成树G的生成树如果G是连通(n,m)图,则可分为:T(n,n-1)+(m-n+1)边树枝弦19定理12.7设无向图G是连通的,则G至少有一个生成树.GG1x1G2x2G3x3G4x4G5=TG去圈法如果每次将一条弦加到生成树TG上，就会得到由树枝和这条弦构成的唯一的一个圈，称为基本圈共有m－n＋1个。20设G为带权连通无向图,每边的权为C(e).C(TG)为生成树TG所有树枝的权的和.定义12.8设G是带权连通无向图,在G的所有生成树中,权值最小的树称为G的最小生成树.方法1:去圈法先选权最大的边,如果该边在圈中,则去掉该边.1211361097854带权连通无向图12361097854丢最大权边去圈12375最小生成树21方法2:选边避圈法(Kruskal)循环选权最小的边,并保证不产生圈.⑴选取最小权边e1,i←1;⑵若i=n-1,则终止,否则执行(3);⑶设已选边{e1,e2,…,ei},在G剩余的边中选ei+1,使得加入新边后不产生圈且ei+1是剩余边中权最小;⑷i←i+1,转⑵继续.1211361097854带权连通无向图1选最小边且无圈12375最小生成树22⑴设依上法构造的导出子图为T,则T无圈且m=n-1,所以T是生成树.⑵设T*是图G的最小生成树,如果T与T*不同,可设T与T*有{e1,e2,…,ei}共i条公共边,但ei+1T,ei+1T*.按权排列---选边的顺序因T*是树,T*+ei+1必有圈.同样T也是树,所以圈必有边不在T中---设此边为x.构造新树T’---将T*中的边x换成ei+1,则C(T’)=C(T*)+C(ei+1)–C(x)因T*是最小生成树,故C(T’)≥C(T*),可得C(ei+1)≥C(x),如果C(ei+1)C(x),则与T的选边方法不符,故C(ei+1)=C(x).于是T’也是最小生成树,且T’与T的公共边比T*与T的公共边多了一条.循环下去,将T’看作是新的T*,每次都使公共边多一条,最后完全相同,即得T也是最小生成树.23§12.5割集割点割边(桥)去掉它,原来的连通无向图就不再连通定义12.9设G=V,E为连通无向图,如果G中有边集E’E,把E’中所有边去掉将使图G分离为两个连通分支,但去掉E’中任一真子集,图G仍将连通,则称E’为图G的一个割集.u1u2u3u4e1e2e3e4e5e6e7e8u1u2u3u4e2e3e8割集:{e1,e4,e5,e6,e7}24割集的另一种说法:对于无向连通图G,把G的顶点分成两个不相交的子集(划分),使每一子集的导出子图是连通的,则将这两个子集中的顶点连接起来的边集,是图的一个割集.割集与生成树:去掉生成树中任一条树枝(树的割边),即能产生两个顶点子集(这两个子集的导出子图是连通的).所以,生成树TG中的每条树枝再加上求生成树时去掉的各边,即构成图G的一个割集---称为对应于该条树枝的基本割集.这些基本割集即构成基本割集组.对应于不同的生成树，其对应的基本割集组是不同的。25u1u2u3u4e1e2e3e4e5e6e7e8u1u2u3u4e2e3e8e6树枝e2,e8,e6,e3对应的基本割集分别是：D1＝{e1,e5,e2}D2＝{e1,e4,e8}D3＝{e1,e4,e5,e6,e7}D4＝{e3,e4,e7}u1u2u3u4e1e2e3e4e5e6e7e8u1u2u3u4e1e2e5e7树枝e1,e2,e5,e7对应的基本割集分别是：D1＝{e1,e4,e8}D2＝{e2,e6,e3}D3＝{e3,e4,e5,e6,e8}D4＝{e3,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定理12.12图G的生成树TG,设C={e1,e2,…,ek}是一个基本圈,其中e1是弦,e2,e3,…,ek是树枝,则e1包含在对应于e2,…,ek的基本割集中,但e1不包含在任何其它的基本割集中.证明与定理12.11类似。