《数学建模 简单.pptx》由会员分享，可在线阅读，更多相关《数学建模 简单.pptx（113页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、引言 图论是离散数学的重要组成部分，是近代应用数学的重要分支。人们常称1736年是图论历史元年，因为在这一年瑞士数学家欧拉（Euler）发表了图论的首篇论文哥尼斯堡七桥问题无解，所以人们普遍认为欧拉是图论的创始人。1936年，匈牙利数学家寇尼格（Konig）出版了图论的第一部专著有限图与无限图理论，这第1页/共113页是图论发展史上的重要的里程碑，它标志着图论将进入突飞猛进发展的新阶段。随着计算机科学的发展，图论更以惊人的速度向前发展，有人形容说：真是异军突起，活跃非凡。其主要原因有二：其一，计算机科学的发展为图论的发展提供了计算工具；其二，现代科学技术的发展需要借助图论来描述和解决各类课题中
2、的各种关系，从而推动科学技术不断地攀登新的高峰。第2页/共113页 作为描述事务之间关系的手段或称工具，目前，图论在许多领域，如计算机科学、物理学、化学、运筹学、信息论、控制论、网络通讯、社会科学以及经济管理、军事、国防、工农业生产等方面都得到广泛的应用，也正是因为在众多方面的应用中，图论自身才得到了非常迅速的发展。本部分主要包括图的基本概念（第十四章）、欧拉图与哈密顿图（第十五章）、树（第十六章）、平面图及图的着色（第十七章）、支配集、覆盖集、独立集与匹配（第十八章）。第3页/共113页 第十四章 图 的 基 本 概 念第4页/共113页14.1图一无向图与有向图1无向图一个无向图是一个有序
3、的二元组,记作G，其中（1）V是非空有限集合，称为顶点集，其元素称为G的顶点或结点。（2）E是有限集合，称为边集，其元素是V上多重的二元无序对，称为G的无向边，简称边。说明:多重集(P.227,注)第5页/共113页 2.有向图一个有向图是一个有序的二元组，记作D，其中（1）V是非空有限集合，称为顶点集，其元素称为G的顶点或结点。（2）E是有限集合，称为边集，其元素是V上多重的二元有序对，称为G的有向边，简称边。3.图的表示无向图和有向图也可用图形来表示，用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。第6页/共113页P.268 例14.1(1)给定无向图
4、G=，其中V=v1,v2,v3,v4,v5，E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).(2)给定有向图D=，其中，V=a,b,c,d，E=,.画出G与D的图形。解:图14.1中(1),(2)分别给出了无向图G和有向图D的图形。第7页/共113页v v1 1v v2 2v v3 3v v4 4v v5 5e e1 1e e2 2e e3 3e e4 4e e5 5e e6 6e e7 7图图14.1(a)14.1(a)第8页/共113页a ab bc cd de e1 1e e2 2e e3 3e e4 4e e5 5e
5、e6 6e e7 7图图14.1(b)14.1(b)注注:书中有错书中有错第9页/共113页二、与图有关的其它概念1n阶图若图G(无向的或有向的)含有n个顶点，则称G为n阶图。2关联设G=为图(无向的或有向的)，边ek=(vi，vj)(或ek=)E，称vi，vj为ek的端点(vi是ek的始点,vj是ek的终点),称ek与vi、vj是彼此相关联的。第10页/共113页3环若边ek=(vi，vj)(或ek=)中，vi=vj，则称ek为环。孤立点不与任何边关联的顶点称孤立点。相邻与邻接设图G=无向图(有向图)，vi，vjV，若etE，使得et=（vi，vj）(et=)，则称vi与vj是相邻的(vi邻
6、接到vj，vj邻接于vi)有向图中,若ek的终点为el的始点，则称ek与el相邻。第11页/共113页无向图中,若边ek与el至少有一个公共端点，则称ek与el是相邻的。三多重图与简单图1 平行边与边的重数 在无向图中，关联一对顶点的无向边如果多于1条，则称这些边为平行边，平行边的条数称为重数。在有向图中，关联一对顶点的有向边如果多于1条，并且这些边的始点和终点相同(也就是它们的方向相同)，则称这些边为平行边。第12页/共113页2多重图与简单图 含平行边的图称为多重图，既不含平行边也不含环的图称为简单图。四、顶点的度数与握手定理1顶点的度数设G=为一无向图，vV，v作为边的端点次数之和称为v
7、的度数，简称为度，记做dG(v)，或d(v).第13页/共113页设D=为有向图，vV，v作为边的始点次数之和为称v的出度，记做，或d+(v).v作为边的终点次数之和称为v的入度，记做或d-(v)，称d+(v)+d-(v)为v的度数，记做d(v).最大度和最小度 在图G中，称(G)=maxd(v)|vV(G)和(G)=mind(v)|vV(G)，分别为G的最大度和最小度。分别简记为和.第14页/共113页悬挂点与悬挂边称度数为1的顶点为悬挂顶点，与它关联的边称为悬挂边。奇度顶点与偶度顶点度为偶数(奇数)的顶点称为偶度(奇度)顶点。握手定理(1).设G=为无向图,V=v1,v2,vn，|E|=m
8、，则第15页/共113页证明:G中每条边(包括环)均有两个端点，所以在计算G中各顶点度数之和时，每条边均提供2度，因此m条边，共提供2m度。(2).设D=为有向图，V=v1,v2,vn，|E|=m，则证明：类似于（1）第16页/共113页(3).推论:任何图(无向的或有向的)中，奇度顶点的个数是偶数。证明:设G=为任意一图，令:V1=v|vVd(v)为奇数V2=v|vVd(v)为偶数则V1V2=V，V1V2=，由握手定理可知第17页/共113页五、度数列与非负整数列的可图化1、度数列设G=为一个n阶图,V=v1,v2,vn,称d(v1),d(v2),d(vn)为G的度数列。若G为有向图，称d+
9、(v1),d+(v2),d+(vn)与d-(v1),d-(v2),d-(vn)分别为G的出度列和入度列。例 在图14.1(a)中，按顶点的标定顺序，度数列为4,4,2,1,3.在(b)中，按字母顺序，度数列，出度列，入度列分别为5,3,3,3；4,0,2,1；1,3,1,2.第18页/共113页2、非负整数列的可图化（1）可图化的概念对于给定的非负整数列d=(d1,d2,dn)，若存在以V=v1,v2,vn为顶点集的n阶无向图G，使得d(vi)=di，则称d是可图化的。特别地，若所得图是简单图，则称d是可简单图化的。（2）可图化的判定定理非负整数列d=(d1，d2，dn)是可图化的当且仅当第1
10、9页/共113页(3，3，2，1)，(3，2，2，1，1)都是不可图化的，(3，3，2，2)，(3，2，2，2，1)都是可图化的。显然，如此做出的图可能不是简单图，对于可图化的非负整数列d=(d1,d2,dn)，能否简单图化?这可由如下结论判定:若G为n阶无向简单图，则(G)n1.因此,d1=(5,4,3,2,2)、d2=(4,4,3,3,2,2)都可图化,但d1不可简单图化，d2可简单图化。第20页/共113页P.272 例142判断下列各非负整数列哪些是可图化的？哪些是可简单图化的？(1).(5,5,4,4,2,1)(2).(5,4,3,2,2)(3).(3,3,3,1)(4).(4,4,
11、3,3,2,2)(5).(d1,d2,dn)，d1d2dn1且di为偶数.解:易知，除(1)中序列不可图化外，其余各序列都可图化。但除了(4)中序列外，其余的都是不可简单图化的。(2)中序列有5个数，若它可简单图化，设所得图为G，则(G)=max5,4,3,2,2=5，这与定理矛盾。第21页/共113页所以(2)中序列不可简单图化。类似可证(5)中序列不可简单图化。假设(3)中序列可以简单图化，设G=是以(3)中序列为度数列的简单图。不妨设V=v1，v2，v3，v4，且d(v1)=d(v2)=d(v3)=3,d(v4)=1，由于d(v4)1，因而v4只能与v1，v2，v3之一相邻，于是v1，v
12、2，v3不可能都是3度顶点，这是矛盾的，因而(3)中序列也不可简单图化。第22页/共113页(4)中序列是可简单图化的，图14.2中两个6 阶无向简单图都以(4)中序列为度数列。图图14.214.2第23页/共113页六、图的同构 1同构的定义设G1=，G2=为两个无向图(有向图)，若存在双射函数f：V1V2，使得对于任意vi，vjV1，(vi，vj)E1(E1)当且仅当(f(vi)，f(vj)E2(E2)，并且(vi，vj)()与(f(vi)，f(vj)()的重数相同，则称G1与G2是同构的，记做G1G2.第24页/共113页在下图中，(1)为彼得松(Petersen)图，(2)，(3)均与
13、(1)同构。(4)，(5)，(6)各图彼此间都不同构。第25页/共113页一般说来，证明两个图是同构的并非是轻而易举的事情，往往需要花些气力。寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。根据图同构的定义，可以给出图同构的必要条件：(1)结点数目相等；(2)边数相等；(3)度数相同的结点数目相等。但这仅仅是必要条件而不是充分条件。第26页/共113页例如下图中的(a)与(b)满足上述三个条件,然而并不同构.因为在(a)中度数为3的结点x与两个度数为1的结点邻接，而(b)中度数为3的结点Y仅与一个度数为1的结点邻接。ABECDY (a)(b)(a)(b)abcdex第2
14、7页/共113页七、完全图与正则图 1完全图设G为n阶简单图，若G中任两个顶点均有边关联,则称G为n阶完全图。n阶无向完全图记做Kn(n1)。2.竞赛图设D为n阶有向简单图，若D的基图为n阶无向完全图Kn，则称D是n阶竞赛图。第28页/共113页在图14.4中，(1)为K5，(2)为3阶有向完全图，(3)为4阶竞赛图。图14.4第29页/共113页易知，n阶无向完全图，n阶有向完全图，n阶竞赛图的边数分别为n(n-1)/2，n(n1)，n(n-1)/2.3正则图设G为n阶无向简单图，若vV(G)，均有d(v)=k，则称G为k-正则图。由定义可知，n阶零图是0-正则图，n阶无向完全图是(n-1)
15、正则图，彼得松图是3-正则图。由握手定理可知，n阶k-正则图中，边数m=kn/2，因而当k为奇数时，n必为偶数。第30页/共113页八、子图与补图 1子图与导出子图设G=，G=为两个图(同为无向图或同为有向图)，若VV且EE，则称G是G的子图，G为G的母图，记作GG.又若VV或EE，则称G为G的真子图。若V=V，则称G为G的生成子图。设G=为一图，V1V且V1，称以V1为顶点集，以G中两个端点都在V1中的边组成边集E1的图为G的V1导出的子图，记作GV1.第31页/共113页又设E1E且E1，称以E1为边集，以E1中边关联的顶点为顶点集V1的图为G的E1导出的子图，记作GE1.在图14.5中，
16、设G为(1)中图所表示，取V1=a，b，c，则V1的导出子图GV1为(2)中图所示。取E1=e1，e3，则E1的导出子图GE1为(3)中图所示。第32页/共113页图图14.514.5第33页/共113页14.2通路与回路 一通路与回路的定义设G为标定图，G中顶点与边的交替序列第34页/共113页中边的条数称为它的长度。若，则称通路为回路。若的所有边各异，则称为简单通路，又若，则称为简单回路。若的所有顶点(除可能相同外)各异，所有边也各异，则称为初级通路或路径，此时又若，则称为初级回路或圈。将长度为奇数的圈称为奇圈，长度为偶数的圈称为偶圈。第35页/共113页二.n阶图中通路与回路的性质 定理
17、1在n阶图G中，若从顶点vi到vj（vivj）存在通路，则从vi到vj存在长度小于或等于（n-1）的通路。（可得到初级通路）定理2在n阶图G中，若存在vi到自身的回路，则一定存在vi到自身的长度小于或等于n的回路。若存在vi到自身的简单回路，则一定存在vi到自身的长度小于或等于n的初级回路。第36页/共113页14.3图的连通性一、无向图的连通性1、设无向图G=,u,vV，若u,v之间存在通路，则称u,v是连通的，记作uv.vV，规定vv.显然，=（u,v）|u,vV且u与v之间有通路是V上的等价关系。2、若无向图G是平凡图或G中任何两个顶点都是连通的，则称G为连通图，否则称G是非连通图或分离
18、图。第37页/共113页3、设无向图G=，V关于顶点之间的连通关系的商集V/=V1,V2,Vk，Vi为等价类，称导出子图GVi(i=1,2,k)为G的连通分支，连通分支数k常记为p(G).二、无向图的割集1、设无向图G=，若存在VV，且V，使得p(G-V)p(G)，而对于任意的VV，均有p(G-V)=p(G)，则称V是G的点割集.若V是单元集，即V=v，则称v为割点。第38页/共113页图14.8例，在中v2,v4，v3，v5都是点割集，而v3,v5都是割点。注意，v1与悬挂顶点v6不在任何割集中。第39页/共113页2、设无向图G=，若存在EE，且E，使得p(G-E)p(G)，而对于任意的E
19、E，均有p(G-E)=p(G)，则称E是G的边割集，或简称为割集。若E是单元集，即E=e，则称e为割边或桥。例在图14.8中，e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集，其中e6,e5是桥。第40页/共113页三、有向图的连通性1、设D=为一个有向图，vi,vjV，若从vi到vj存在通路，则称vi可达vj，记作vivj规定每个顶点到自身总是可达的若vi与vj是相互可达的，则记作vivj.2、设D=为有向图，vi,vjV，若vivj，则称vi到vj长度最短的通路为vi到vj的短程线，短程线的长度为vi到vj的距离，记作d.第41页/共113页3、设
20、D=为一个有向图，若D的基图是连通图，则称D是弱连通图，简称为连通图。若vi,vjV，vivj与vjvi至少成立其一，则称D是单向连通图。若vi,vjV均有vivj，则称D是强连通图。显然，强连通图一定是单向连通图，单向连通图一定是弱连通图。第42页/共113页图14.11 在图14.11中，（1）为强连通图，（2）为单连通图，（3）是弱连通图。第43页/共113页4、有向图连通性的判定定理给定n阶有向图D=，设=v1,v2,vn.则D是强连通图当且仅当D中存在经过每个顶点至少一次的回路；D是单向连通图当且仅当D中存在经过每个顶点至少一次的通路。证明：（略）第44页/共113页14.4图的矩阵
21、表示一、关联矩阵1.无向图的关联矩阵设无向图G=，V=v1,v2,vn，E=e1,e2,em，令mij为顶点vi与边ej的关联次数，则称(mij)nm为G的关联矩阵，记作M(G).例求图14.14的关联矩阵第45页/共113页图图 14.1414.14第46页/共113页第47页/共113页2.无向图关联矩阵M(G)的性质:第48页/共113页3.有向图的关联矩阵设有向图D=中无环，V=v1,v2,vn，E=e1,e2,em,令则称(mij)nm为D的关联矩阵，记作M(D).例求下图的关联矩阵第49页/共113页解:第50页/共113页4.有向图关联矩阵的性质二、有向图的邻接矩阵 1.设有向图
22、D=，V=v1,v2,vn，E=e1,e2,，em，令为顶点vi邻接到顶点vj边的条数，称为D的邻接矩阵，记作A(D)，或简记为A.第51页/共113页第52页/共113页2.有向图邻接矩阵的性质第53页/共113页3.A(D)次幂的元素的意义例给定有向图如右,问从顶点v2到v4长度为3的通路有几条?从顶点v1到v3长度不超过4的通路有几条?第54页/共113页由A3中元素可知,D中从v2到v4长度为3的路有1条.由A,A2,A3,A4中(1,3)元素之和可得,从顶点v1到v3长度不超过4的通路有1+2+1+3=7条第55页/共113页三、有向图的可达矩阵1.2.可达矩阵的求法(1).P=A0
23、VA1VA2VVan(2).Warshall算法第56页/共113页 第十五章 欧拉图与哈密顿图第57页/共113页15.1欧拉图一、问题的提起1736年瑞士数学家欧拉(Euler)发表了图论的第一篇著名论文“哥尼斯堡七桥问题”。这个问题是这样的：哥尼斯堡城有一条横贯全城的普雷格尔河，城的各部分用七桥联结，每逢节假日，有些城市居民进行环城周游，于是便产生了能否“从某地出发，通过每桥恰好一次，在走遍了七桥后又返回到原处”的问题。如图15.5(a)第58页/共113页图图15.515.5（b)b)图图15.515.5（a)a)第59页/共113页欧拉将图15.5(a)简化为图15.5(b),论证了
24、该问题无解.二、欧拉图、半欧拉图1、欧拉图、半欧拉图定义通过图（无向图或有向图）中所有边一次且仅一次行遍图中所有顶点的通路称为欧拉通路，通过图中所有边一次并且仅一次行遍所有顶点的回路称为欧拉回路。具有欧拉回路的图称为欧拉图，具有欧拉通路而无欧拉回路的图称为半欧拉图。第60页/共113页 2、欧拉图、半欧拉图的判定（1）无向图G是欧拉图当且仅当G是连通图，且G中没有奇度顶点。（2）无向图G是半欧拉图当且仅当G是连通的，且G中恰有两个奇度顶点。（3）有向图D是欧拉图当且仅当D是强连通的且每个顶点的入度都等于出度。（4）有向图D是半欧拉图当且仅当D是单向连通的，且D中恰有两个奇度顶点，其中一个的入度
25、比出度大1，另一个的出度比入度大1，而其余顶点的入度都等于出度。第61页/共113页3、求欧拉回路的Fleury算法(能不走桥就不走桥)（1）任取v0V(G)，令P0=v0.（2）设Pi=v0e1v1e2eivi已经行遍，按下面方法从E(G)-e1,e2,ei中选取ei+1：（a）ei+1与vi相关联；（b）除非无别的边可供行遍，否则ei+1不应该为Gi=G-e1,e2,ei中的桥。（3）当（2）不能再进行时，算法停止。可以证明，当算法停止时所得简单回路Pm=v0e1v1e2emvm(vm=v0)为G中一条欧拉回路。第62页/共113页 例:上图(1)是给定的欧拉图G。某人用Fleury算法求
26、G中的欧拉回路时，走了简单回路v2e2v3e3v4e14v9e10v2e1v1e8v8e9v2之后，无法行遍了，试分析在哪步他犯了错误?第63页/共113页解：此人行遍v8时犯了能不走桥就不走桥的错误，因而他没行遍出欧拉回路。当他走到v8时，G6=G-e2,e3,e14,e10,e1,e8为图(2)所示。此时e9为该图中的桥，而e7,e11均不是桥，他不应该走e9，而应该走e7或e11，他没有走，所以犯了错误。注意，此人在行遍中，在v3遇到过桥e3，v1处遇到过桥e8，但当时除桥外他无别的边可走，所以当时均走了桥，这是不会犯错误的。第64页/共113页15.2哈密顿图 一、问题的提起1859年
27、，爱尔兰数学家哈密顿(Hamilton)首先提出“环球周游”问题。他用一个正十二面体的20个顶点代表世界上20个大城市(见下图1)，这个正十二面体同构于一个平面图(见下图2)（平面图的定义见第17章17.1节)。问:“旅游者能否找到沿着正十二面体的棱，从某个顶点出发，经过每个顶点恰好一次，然后回到出发顶点”?这便是著名的哈密顿问题。第65页/共113页图1图2第66页/共113页二、哈密顿图、半哈密顿图1、哈密顿图、半哈密顿图的定义经过图（有向图或无向图）中所有顶点一次且仅一次的通路称为哈密顿通路。经过图中所有顶点一次且仅一次的回路称为哈密顿回路。具有哈密顿回路的图称为哈密顿图，具有哈密顿通路
28、但不具有哈密顿回路的图称为半哈密顿图。第67页/共113页2、哈密顿图、半哈密顿图的判定（1）设G是n阶无向简单图，若对于G中任意不相邻的顶点vi,vj，均有d(vi)+d(vj)n-1，则G为半密顿图。（2）设G为n(n3)阶无向简单图，若对于G中任意两个不相邻的顶点vi,vj，均有d(vi)+d(vj)n则G为哈密顿图。第68页/共113页例：在某次国际会议的预备会议中，共有8人参加，他们来自不同的国家。已知他们中任何两个无共同语言的人中的每一个，与其余有共同语言的人数之和大于或等于8，问能否将这8个人排在圆桌旁，使其任何人都能与两边的人交谈。解：设8个人分别为v1,v2,v8，令V=v1
29、,v2,v8.vi,vjV（ij），若vi与vj有共同语言，就在vi,vj之间连无向边（vi,vj），由此组成边集合E，从而得8阶无向简单图G=。第69页/共113页viV，d(vi)为与vi有共同语言的人数。由已知条件可知，vi,vjV且ij，均有d(vi)+d(vj)8.由判定定理（2），G为哈密顿图，从而存在哈密顿回路，按这样的回路上各顶点的顺序安排座次即可。第70页/共113页16.1无向树及其性质 一、无向树的定义连通无回路的无向图称为无向树，或简称树，常用T表示树。若无向图G至少有两个连通分支，每个连通都是树，则称G为森林。在无向图中，悬挂顶点称为树叶，度数大于或等于2的顶点称为分
30、支点。二、无向树的性质第71页/共113页定理1设G=是n阶m条边的无向图，则下面各命题是等价的：（1）G是树。（2）G中任意两个顶点之间存在唯一的路径。（3）G中无回路且m=n-1.（4）G是连通的且m=n-1.（5）G是连通的且G中任何边均为桥。（6）G中没有回路，但在任何两个不同的顶点之间加一条新边，在所得图中得到唯一的一个含新边的圈。第72页/共113页证明:（1）（2）.由G的连通性可知，u,vV，u与v之间存在路径.若路径不是唯一的，设1与2都是u到v的路径，易知必存在由1和2上的边构成的回路，这与G中无回路矛盾。（2）（3）.首先证明G中无回路。若G中存在关联某顶点v的环，则v到
31、v存在长为0和1的两条路径，这与已知矛盾。若G中存在长度大于或等于2的圈，则圈上任何两个顶点之间都存在两条不同的路径，这也引出矛盾。下面用归纳法证明m=n-1.第73页/共113页n=1时，由于G中无回路,故G为平凡图，m=0=n-1,结论成立。设nk(k1)时结论成立，则当n=k+1时，设e=(u,v)为G中的一条边，由于G中无回路，所以G-e为两个连通分支G1,G2.设ni,mi分别为Gi中的顶点数和边数，则nik，由归纳假设可知mi=ni-1，i=1,2.于是m=m1+m2+1=n1-1+n2-1=n1+n2-1=n-1.结论成立.由归纳法原理,对一切正整数n结论成立.第74页/共113
32、页（3）（4）.只要证明G是连通的。否则设G有s（s2）个连通分支G1,G2,Gs.Gi中均无回路，因而Gi全为树，由(1)(2)(3)可知，mi=ni-1,(i=1,2.,s).于是，由于s2，这与m=n-1矛盾。（4）（5）.只要证明G中每条边均为桥，eE，均有|E(G-e)|=n-1-1=n-2，由习题十四题49可知，G-e已不是连通图，故e为桥。第75页/共113页（5）（6）.由于G中每条边均为桥，因而G中无圈，又由于G连通，所以G为树，由（1）（2）可知，u,vV且uv，则u与v之间存在唯一的路径，则（u,v）（u,v）为加的新边）为G中的圈，显然圈是唯一的。（6）（1）.只要证明
33、G是连通的。u,vV且uv，则新边（u,v）G产生唯一的圈，显然有C-(u,v)为G中u到v的通路，故uv，由u,v的任意性可知，G是连通的。第76页/共113页定理2设T是n阶非平凡的无向树，则T中至少有两片树叶。证明:设T有x片树叶，由握手定理及定理1可知，2(n-1)=d(vi)x+2(n-x)由上式解出x2.以上两个定理给出了无向树的主要性质，利用这些性质和握手定理，可以画出阶数n比较小的所有非同构的无向树。第77页/共113页P.307 例16.1画出6阶所有非同构的无向树。解:设Ti是6阶无向树。定理1可知，Ti的边数mi=5，由握手定理可知，dTi(vi)=10，且(Ti)1，(
34、Ti)5.于是Ti的度数列必为以下情况之一。（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.第78页/共113页其中(i)对应Ti,i=1,2,3,（4）对应两棵非同构的树T4，T5，(5)对应T6第79页/共113页P.308 例16.27阶无向图有3片树叶和1个3度顶点，其余3个顶点的度数均无1和3.试画出满足要求的所有非同构的无向树。解:设Ti为满足要求的无向树，则边数mi=6，于是dTi(vi)=12=13+3+d(v5)+d(v6)+d(v7).所以,d(v5)+d(v6)+d(v7
35、)=6.由于d(vj)1d(vj)3，而且1d(vj)6，j=5,6,7可知d(vj)=2，j=4,5,6.于是Ti的度数列为1，1，1，2，2，2，3与3度顶点邻接的3个顶点其度数列有4种情形:第80页/共113页1,1,1;1,1,2;1,2,2;2,2,2.但1,1,1是不可能的,否则,Ti不是连通图,与Ti是树矛盾.因此,所求的非同构的7阶无向树只有3棵,如下图所示.第81页/共113页16.2生成树一、生成树的定义设T是无向图G的生成子图，若T为树，则称T为G的生成树。二、生成树的存在定理无向图G具有生成树，当且仅当G是连通图。证明：必要性显然。只需证明充分性。若G中无回路，则G为树
36、，即为自己的生成树。若G中含有圈，任取一圈，随意地删除圈上的一条边，若第82页/共113页再有圈再删除圈上的一条边，直到最后无圈为止，易知所得G的生成子图无圈且连通，所以为G的生成树。三、生成树的应用最小生成树1、最小生成树的定义设无向连通带权图G=，T是G的一棵生成树。T的各边权之和称为T的权，记作W(T).G的所有生成树中权最小的生成树称为G的最小生成树。第83页/共113页2、求最小生成树的避圈法（Kruskal算法）。设n阶无向连通带权图G=有m条边，不妨设G中没有环（否则，可以将所有的环先删去），将m条边按权从小到大顺序排列，设为e1,e2,em.取最小的两条边e1,e2构成边的集合
37、T=e1,e2.从e3起依次检查e3,em.若ej与T中的边不能构成回路，则将ej加入T中，否则不将ej加入T中.最后得到n-1条边的集合T=e1,e2,en-1.就是G的最小生成树.第84页/共113页(1)j1,T,(2)若Tej导出的子图中不包含简单回路,则TTej,(3)若T中已有n-1条边,则算法停止,否则jj+1,转至(2).这一算法的正确性证明如下.设T0是按上述方法构成的一个图,因为T0不含回路,所以T0是树.又因为T0的n-1条边关联图G的n个顶点,所以T0是G的一棵生成树.第85页/共113页假设G的最小生成树是T且TT0,要证W(T)=W(T0)因为TT0,所以存在T0中
38、的边而不在T中.取权数最小的这样的边设为ei.即设e1,e2,ei-1是T0、T的公共边,eiT0eiT，1in-2将ei加入到T上必构成一基本回路R,去掉R中不是e1,e2,ei-1,ei的一条边a(这样的边必存在，否则,e1,e2,ei-1,ei中存在回路，矛盾）因此，可得G的生成树T1=(Tei)-a.显然，W(a)W(ei)且W(T1)=W(T)+W(ei)-W(a)因为T是最小生成树,所以W(T)W(T1),故W(ei)W(a).所以W(e1)=W(a).从而W(T1)=W(T),第86页/共113页即T1也是G的最小生成树,且与T0有了i条公共边e1,e2,ei-1,ei.用T1取
39、代T(即这时的T是G的最小生成树,且与T0有了i条公共边e1,e2,ei-1,ei.)重复上述做法，直到与T0有n-1条公共边为止，于是T0与T有完全相同的边，T0也就是最小生成树。(注:这里要求G的各边权数互不相同,所得的最小生成树是唯一的)例P.311第87页/共113页16.3根树及其应用 一、根树1、设D是有向图，若D的基图是无向树，则称D为有向树。2、设T是n（n2）阶有向图，若T中有一个顶点的入度为0，其余的顶点的入度均为1，则称T为根树。3、根树T中，入度为0的顶点称为树根，入度为1出度为0的顶点称为树叶，入度为1出度不为0的顶点称为内点，内点和树根统称为分支点。第88页/共11
40、3页4、从树根到T的任意顶点v的通路（路径）长度称为v的层数，层数最大顶点的层数称为树高。将平凡树也称为根树。二、根树的表示1、在根树中，由于各有向边的方向是一致的，所以画根树时可以省去各边上的所有箭头，并将树根画在最上方。例第89页/共113页第90页/共113页2、设T为一棵非平凡的根树，vi,vjV(T)，若vi可达vj，则称vi为vj的祖先，vj为vi的后代；若vi邻接到vj（即E(T)），则称vi为vj的父亲，而vj为vi的儿子。若vj,vk的父亲相同，则称vj与vk是兄弟。3、设T为根树，若将T中层数相同的顶点都标定次序，则称T为有序树。三、根树的分类1、若T的每个分支点至多有r个
41、儿子，则称T为r叉树；又若r叉树是有序的，则称它为r叉有序树。第91页/共113页2、若T的每个分支点都恰好有r个儿子，则称T为r叉正则树；又若T是有序的，则称它为r叉正则有序树。3、若T是r叉正则树，且每个树叶的层数均为树高，则称T为r叉完全正则树，又若T是有序的，则称它为r叉完全正则有序树。4、设T为一棵根树，vV(T)，称v及其后代的导出子图Tv为T的以v为根的根子树。5、2叉正则有序树的每个分支点的两个儿子导出的根子树分别称为左子树和右子树。第92页/共113页四、最优树1、2叉树的权设2叉树T有t片树叶v1,v2,vt，权分别为w1,w2,wt，称W(t)=wil(vi)为T的权，其
42、中l(vi)是vi的层数。2、最优2叉树在所有有t片树叶，带权w1,w2,wt的2叉树中，权最小的2叉树称为最优2叉树。例：T1,T2,T3都是带权为2,2,3,3,5的2叉树（下图所示），它们的权分别是第93页/共113页W(TW(T1 1)=22+22+33+53+32=38)=22+22+33+53+32=38W(TW(T2 2)=34+54+33+22+21=47)=34+54+33+22+21=47W(TW(T3 3)=33+33+52+22+22=36)=33+33+52+22+22=36第94页/共113页3、求最优2叉树的Huffman算法给定实数w1,w2,wt，且w1w2w
43、t.求以w1,w2,wt为树叶权的最优2叉树.(1).连接权为w1,w2的两片树叶，得一个分支点，其权为w1+w2.(2).在w1+w2,w3,wt中选出两个最小的权，连接它们对应的顶点（不一定是树叶），得新分支点及所带的权。(3).重复(2)，直到形成t-1个分支点，t片树叶为止。所得2叉树即为最优2叉树.第95页/共113页上述算法的正确性基于如下两个定理1.设T是树叶权为w1w2wt的最优树,则权最小的两片树叶是兄弟且其路径长度最长.2.设T是树叶权为w1w2wt.的最优树,去掉带最小权w1,w2的两片树叶,使它们的父亲为带权w1+w2的树叶,得到一棵新的带权二元树T,则T也是最优树.第
44、96页/共113页例16.4求带权2,2,3,3,5的最优2叉树。解:下图给出了计算最优树的过程。最优树为（4）所示，W(T)=34。第97页/共113页五、最佳前缀码 1、前缀码设12n-1n为长为n的符号串，称其子串1，12，12n-1分别为该符号串的长度为1，2，n-1的前缀。设A=1,2,m为一个符号串集合，若对于任意的i，jA，ij，i，j互不为前缀，则称A为前缀码。若符号串i（i=1,2,m）中只出现0，1两个符号，则称A为二元前缀码。例:1,00,011,0101,01001,01000为前缀码。1,00,011,0101,0100,01001,01000不是前缀码。第98页/共
45、113页2、定理由一棵给定的2叉正则树，可以产生唯一的一个二元前缀码。例：求下图所示两棵2叉树所产生的二元前缀码。第99页/共113页（1 1）的前缀码为）的前缀码为1111，0101，000000，00100010，0011.0011.或或1010，0101，000000，00100010，0011.0011.（2 2）的前缀码为）的前缀码为0101，1010，1111，000000，00100010，0011.0011.第100页/共113页3、最佳前缀码由最优2叉树产生的前缀码称为最佳前缀码，用最佳前缀码传输对应的各符号能使传输的二进制数位最省。例、在通信中，八进制数字出现的频率如下：0
46、：25%1：20%2：15%3：10%4：10%5：10%6：5%7：5%求传输它们的最佳前缀码，并求传输10n（n2）个按上述比例出现的八进制数字需要多少个二进制数字？若使用等长的（长为3）的码子传输需要多少个二进制数字？第101页/共113页解：用100个八进制数字中各数字出现的个数，即以100乘各频率为权，并将权由小到大排列，得w1=5，w2=5，w3=10，w4=10，w5=10，w6=15，w7=20，w8=25（记住它们各对应哪个数字），用Huffman算法求最优树（结果不唯一）。以图（1）为例说明。第102页/共113页第103页/共113页图中矩形框中的符号串为对应数字的码子：
47、01传011 传1001传2100传3101传40001传500000传600001传78个码子的集合01，11，001，100，101，0001，00000，00001为前缀码，而且是最佳前缀码。设（1）中树为T，易知W(T)为传输100个按题中给定的频率出现的八进制数字所用二进制数字个数。W(T)=10+20+35+60+100+40+20=285第104页/共113页因而传输10n（n2）个按题中给定频率出现的八进制数字需要10n-2285=2.8510n个二进制数字.而用长为3的0，1组成的符号串传输10n个八进制数字（如000传0，001传1，111传7）显然用310n个二进制数字，
48、由此可见前缀码节省二进制数字，能提高效率。第105页/共113页六、波兰符号法与逆波兰符号法 1、树的行遍（周游）对于一棵根树的每个顶点都访问一次且仅一次称为行遍或周游一棵树。2、2叉有序正则树三种行遍方式(按树根的位置)：（1）中序行遍法。访问的次序为：左子树、树根、右子树（2）前序行遍法。访问的次序为：树根、左子树、右子树（3）后序行遍法。访问的次序为：左子树、右子树、树根第106页/共113页如上给定的2叉有序正则树T，按不同的行遍方式结果如下：中序行遍：(hdi)be)a(fcg)前序行遍：a(b(dhi)e)(cfg)后序行遍：(hid)eb)(fgc)a其中v表示v为根子树的树根。
49、第107页/共113页3、四则运算式的表示利用2叉有序正则树可以表示四则运算的算式，最高层次的运算符放在树根上，然后依次地将运算符放在根子树的树根上，参加运算的数放在树叶上，并规定被除数、被减数放在左子树树叶上。然后根据不同的访问方法可以得到不同的算法。例：（1）用2叉有序正则树表示下面算式：(a*(b+c)+d*e*f)(g+(h-i)*j)（2）用3种行遍法访问（1）中2叉树，写出访问结果。第108页/共113页解：（1）表示原算式的2叉树为+*+-a ab bc cd de ef fh hi ij jg g第109页/共113页（2）中序行遍法访问结果为：(a*(b+c)+d*(e*f)
50、(g+(h-i)*j)(16.1)前序行遍法访问结果为：(+*a(+bc)(*d(*ef)(+g(*(-hi)j)(16.2)后序行遍法访问结果为：(a(bc+)*)(d(ef*)*)+)(g(hi-)j*)+)(16.3)在（16.1）中，利用四则运算规则省去一些括号，得到原算式，所以中序行遍法访问结果是还原算式。第110页/共113页5、波兰符号法消去（16.2）中的全部括号，得：+*a+bc*d*ef+g*-hij(16.4)如果在（16.4）中规定，每个运算符与它后面紧邻的两个数进行运算，其运算结果是正确的。在这种算法中，由于运算符在参加运算的两个数之前，所以称为前缀符号或波兰符号法。