离散数学图论

信息科学与工程学院1上节知识回顾图G=V,E，其中V是非空点集，E是边集无向图有向图连通图非连通图树：是一种特殊的图无向树有向树信息科学与工程学院2上节知识回顾7-7无向树及其性质定义7-7.1连通无回路的无向图称为无向树，简称树,常用T表示树。平凡图称为平凡树。若无向图G的每个连通分支都是树，则称G为森林。在无向树中，度为1的结点称为树叶，度数大于或等于2的结点称为分枝点或内点。。。。。。。。。。。。。。。信息科学与工程学院3上节知识回顾定理7-7.1设G=V,E是n阶m条边的无向图,则下面各命题是等价的：（1）G是树。（2）G中任意两个结点之间有且仅有一条路。（3）G中无回路且m=n-1。（4）G是连通的且m=n-1。(5)G是连通的且G中任何边均为桥。(6)G中没有回路，但在任何两个不同的结点之间加一条新边，在所得的图中得到唯一的一个含新边的圈。。。。。。。信息科学与工程学院47-8根树及其应用1、根树的相关定义2、根树的性质及应用——二叉树、m叉树3、小结本节内容安排信息科学与工程学院5第七章图论定义7-8.1设D是有向图，若不考虑D图边的方向时是一棵无向树，则称D为有向树。V1。V2。V5。V3。V4。V6。V7。V8。V9。如：结点度的概念如前所讲信息科学与工程学院6第七章图论设T是n(n≥2)阶有向树，若T中恰好有一个结点的入度为0，其余结点的入度均为1，则称T为根树定义7-8.2——根树入度为0的结点称为根层次最大结点的层次称为树高入度为1出度为0的结点称为叶出度不为0的结点称为内点或分枝点从树根到T的任意结点v的单向通路长度称为v的层次定义7-8.3：根树包含一个或多个结点，这些结点中某一个称为根，其他所有结点被分成有限个子根树平凡树也称为根树。V1。V2。V5。V3。V4。V6。V7。V8。V9。。。。。。。。。。。。信息科学与工程学院7第七章图论由于各有向边的方向一致，故常省略，并且树根在最上方。V1。V2。V5。V3。V4。V6。V7。V8。V9。V1。V2。V5。V3。V4。V6。V7。V8。V9。。。。。。。。。。V1V2V3V4V5V6V7V8V9在根树中，若将T中层数相同的结点都标定次序，则称T为有序树。根树的不同画法：信息科学与工程学院8第七章图论设T为一棵非平凡的根树，vi,vj∈V(T),若vi可达vj,则称vi为vj的祖先,vj为vi的后代若vi邻接到vj（即vi,vj∈E(T)），则称vi为vj的父亲，而vj为vi的儿子若vj,vk的父亲相同，则称vj与vk是兄弟。补充定义V1。V2。V5。V3。V4。V6。V7。V8。V9。信息科学与工程学院9第七章图论定义7-8.4在根树T中，若每个结点的出度的小于或等于r，则称T为r叉树。若每个结点的出度恰好等于r或0，则称T为完全r叉树。若完全r叉树所有树叶层次相同，则称T为正则r叉树。当r=2时，称为二叉树。信息科学与工程学院10第七章图论例：。。。。。。。。。。。。。。。。二叉树?正则二叉树?请证明在完全二叉树中，边的总数等于2(nt-1)，nt为树叶数。。。。。。。。。完全二叉树?信息科学与工程学院11第七章图论二叉树在实际生活中应用广泛。例如：M和E两人进行象棋比赛，规定一人连胜两盘或共胜三盘即为获胜，则所有可能的比赛结果可用如下二叉树来描述。。。。。。。。。。。。。。。。。。。。在m叉树中，二叉树相对来讲比较容易处理，所以常常把m叉树的问题转换到二叉树上来讨论。比赛开始信息科学与工程学院12第七章图论根树应用1：一棵m叉有序树改写为一棵二叉树方法任何一棵有序树都可以改写为一个对应的二叉树：①除了最左边的分枝结点外，删去所有从每一个结点长出的分枝。在同一层次中，兄弟结点之间用从左到右的有向边连接。②选定二叉树的左儿子和右儿子如下：直接处于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子，依次类推。信息科学与工程学院13第七章图论例：把下面的m叉树改写为二叉树。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。。除了最左边的分枝结点外，删去所有从每一个结点长出的分枝在同一层次中，兄弟结点之间用从左到右的有向边连接直接处于给定结点下面的结点，作为左儿子，对于同一水平线上与给定结点右邻的结点，作为右儿子信息科学与工程学院14第七章图论练习：把下面的有序树改写为二叉树。。。。。。。。。。。。。。。。。。知识点提示：此方法可推广至有序森林到二叉树的转换。此方法具有可逆性。课下自学信息科学与工程学院15第七章图论定理7-8.1设有完全m叉树，共有t片树叶，i个分枝点，则(m-1)i=t-1。证明：完全m叉树中结点总数为:t+i也可表示为mi+1故得(m-1)i=t-1根树应用2：完全m叉树的应用。。。。。。。。。信息科学与工程学院16第七章图论例：有28盏灯，拟用一个电源插座，问至少需要多少块四插座的接线板？解：将四叉树的每个分枝点看作是四插座的接线板，树叶看作是灯，则根据定理7-8.1可知需要9块。请思考？分析：四插座——m叉树——m接线板——分枝点——i灯——树叶——t完全m叉树，有t片树叶，i个分枝点，则(m-1)i=t-1信息科学与工程学院17第七章图论根树应用3：二叉树的应用——最优树问题定义7-8.5在根树中，一个结点的通路长度为从树根到此结点的通路中的边数。分枝点的通路长度称为内部通路长度。树叶的通路长度称为外部通路长度。。。。。。。。。。A信息科学与工程学院18第七章图论定理7-8.2若完全二叉树有n个分枝点，且内部通路长度总和为L，外部通路长度总和为E，则E=L+2n。证明：对分枝点数目n进行归纳证明。当n=1时，如右图所示，L=0，E=2，显然，E=L+2n成立。。。。信息科学与工程学院19第七章图论定理7-8.2若完全二叉树有n个分枝点，且内部通路长度总和为L，外部通路长度总和为E，则E=L+2n。证明：假设n=k-1时成立，即E`=L`+2(k-1)。当n=k时，若删去一个分枝点v(即变为叶)，设v与根的通路长度为t,且v的两个儿子是树叶，得到新树T`。由于T`有k-1个分枝点，则E`=L`+2(k-1)在原树T中，L=L`+tE=E`+2(t+1)-t=E`+t+2。。。。。。。。。即得E=L+2n信息科学与工程学院20第七章图论补充定义给定一组权ω1,ω2,…,ωt，不妨设ω1≤ω2≤…≤ωt。设有一棵二叉树，共有t片树叶，分别带权ω1,ω2,…,ωt，该二叉树称为带权二叉树。信息科学与工程学院21第七章图论定义7-8.6设二叉树T有t片树叶，v1,v2,…,vt权分别为ω1,ω2,…,ωt，称ω(t)=为T的权，其中L(vi)是vi的层数。在所有有t片树叶，带权ω1,ω2,…,ωt的二叉树中，权最小的那棵二叉树称为最优树。tiiivlw1)(例：求二叉树T的权。。。。。。。。。。32335解：ω(T)=……=40是不是最优二叉树呢？？？信息科学与工程学院22第七章图论定理7-8.3设T为带权ω1≤ω2≤…≤ωt的最优树，则(1)带权ω1，ω2的树叶vω1，vω2是兄弟。(2)以树叶vω1，vω2为儿子的分枝点，其通路长度最长。定理7-8.4设T为带权ω1≤ω2≤…≤ωt的最优树，若将以带权ω1，ω2的树叶为儿子的分枝点改为带权ω1+ω2的树叶，得到新树T`,则T`也是最优树。信息科学与工程学院23第七章图论Huffman算法——一种求最优树的算法给定实数ω1,ω2,…,ωt，且ω1≤ω2≤…≤ωt。（1）连接权为ω1,ω2的两片树叶，得一个分枝点，其权为ω1+ω2。（2）在ω1+ω2,ω3,…,ωt中选出两个最小的权，连接它们对应的结点（不一定是树叶），得新分枝点及所带的权。用此算法求上例的最优二叉树。（3）重复（2），直到形成t-1个分枝点，t片树叶为止。信息科学与工程学院24第七章图论共分为四个步骤：。。。235。。。336。。。235。。。336。。。2355。。10。。。。336。。。2355。。1016最优树为(4)所示，ω(T)=37(1)(2)(3)(4)练习：画一棵权为3,4,5,6,7,8,9的最优二叉树，并计算其权。信息科学与工程学院25第七章图论定义7-8.7设12…n-1n为长为n的符号串，称其子串1,12,…,12…n-1分别为该符号串的长度为1,2,…n-1的前缀，设A={β1,β2,…,βm}为一个符号串集合，若对于任意的βi,βj∈A，i≠j,βi,βj互不为前缀，则称A为前缀码，若符号串中βi(i=1,2,…,m)只出现0，1两个符号，则称A为二元前缀码。如：{1,0,10,01,11,001}{abc,cba,bca,bac,acb,cab}{1,00,011,01001,01000}是(二元)前缀码吗？如何产生二元前缀码呢？根树应用4：二叉树的应用——前缀码问题信息科学与工程学院26第七章图论定理7-8.5任意一棵2叉树的树叶可对应一个前缀码。定理7-8.6任意一个前缀码都对应一棵2叉树。用二叉树产生二元前缀码之做法给定一棵2叉树T，设它有t片树叶。设v为T的一个分枝点，则v至少有一个儿子，最多有两个儿子。若v有两个儿子，在由v引出的两条边上，左边的标上0，右边的标上1；若v有一个儿子，在由v引出的边上可标上0，也可标上1。设vi为T的任一片树叶，从树根到vi的通路上各边的标号组成的0，1串组成的符号串放在vi处，t片树叶处的t个符号串组成的集合为一个二元前缀码。信息科学与工程学院27第七章图论由上面做法知，vi处的符号串的前缀均在vi所在的通路上除vi外的结点处达到，因而所得符号串集合为二元前缀码。若T存在单子分枝点，则由T产生的前缀码可能不唯一。若T为正则2叉树，则由T产生的前缀码唯一。注意：因最优2叉树构造的不唯一性，最佳前缀码也可能不唯一，但其各自对应的最优2叉树的权应该相等。信息科学与工程学院28第七章图论练：在某通信系统中，a、b、c、d、e、f、g、h各字符的传输频率依次为25%、20%、15%、10%、10%、10%、5%、5%，求传输的最佳前缀码，并求传输10n(n=2)个按上述比例的字符需要多少个二进制数字？若采用等长编码需要多少个二进制数字？信息科学与工程学院29小结根树的相关定义根树性质及应用m叉有序树改写为二叉树的方法完全m叉树的应用二叉树的应用——最优树问题有序树，根树，r叉树，完全r叉树，正则r叉树本节作业：P3377-8习题(3)(5)信息科学与工程学院30结束语