图论及其应用ppt7

0.810.60.40.20xt00.511.5210.500.51n1Email:[e-mail]图论及其应用任课教师：杨春数学科学学院0.810.60.40.20xt00.511.5210.500.51n2第二章树本章主要内容一、树的概念与性质二、生成树三、最小生成树授课学时授课学时：6学时0.810.60.40.20xt00.511.5210.500.51n3本次课主要内容(一)、树的概念与应用(二)、树的性质(三)、树的中心与形心0.810.60.40.20xt00.511.5210.500.51n41、树的概念(一)、树的概念与应用定义1不含圈的图称为无圈图，树是连通的无圈图。例如：下面的图均是树树T1树T2树T3树T40.810.60.40.20xt00.511.5210.500.51n5定义2称无圈图G为森林。注:(1)树与森林都是单图;(2)树与森林都是偶图。例1画出所有不同构的6阶树。解：按树中存在的最长路进行枚举。6阶树中能够存在的最长路最小值为2，最大值为5。0.810.60.40.20xt00.511.5210.500.51n6树是图论中应用最为广泛的一类图。在理论上，由于树的简单结构，常常是图论理论研究的“试验田”。在实际问题中，许多实际问题的图论模型就是树。例2族谱图与树2、树的应用要把一个家族的繁衍情况简洁直观表达出来，用点表示家族中成员，成员x是成员y的儿女，把点x画在点y的下方，并连线。如此得到的图，是一颗树，称为根树。示意如下：根树0.810.60.40.20xt00.511.5210.500.51n7实际上，根树是许多问题的模型，如社会结构，计算机数据结构，数学中的公式结构，分类枚举表示等。例3道路的铺设与树假设要在某地建造4个工厂，拟修筑道路连接这4处。经勘探，其道路可按下图的无向边铺设。现在每条边的长度已经测出并标记在图的对应边上，如果我们要求铺设的道路总长度最短，这样既能节省费用，又能缩短工期，如何铺设？v2v3v4e2e3e4v1e1e5e60.810.60.40.20xt00.511.5210.500.51n8该问题归结于在图中求所谓的最小生成树问题。或称为赋权图中的最小连接问题。例4化学中的分子结构与树例如：C4H10的两种同分异构结构图模型为：hhhhhhhhhhhhhhhhhhhh0.810.60.40.20xt00.511.5210.500.51n9例5电网络中独立回路与图的生成树早在19世纪，图论还没有引起人们关注的时候，物理学家克希荷夫就已经注意到电路中的独立回路与该电路中的所谓生成树的关系。即：如果电路是(n,m)图，则独立回路的个数为m-n+1.并且，生成树添上生成树外的G的一条边，就可以得到一独立回路。例6通信网络中的组播树在单播模型中，数据包通过网络沿着单一路径从源主机向目标主机传递，但在组播模型中，组播源向某一组地址传递数据包，而这一地址却代表一个主机组。为了向所有接收者传递数据，一般采用组播分布树描述IP组播在网络里经过的路径。组播分布树有四种基本类型：泛洪法、有源树、有核树和Steiner树。0.810.60.40.20xt00.511.5210.500.51n10总之，树在图论研究和图论应用上都是十分典型的特殊图。定理1每棵非平凡树至少有两片树叶。证明设P=v1v2…vk是非平凡树T中一条最长路，则v1与vk在T中的邻接点只能有一个，否则，要么推出P不是最长路，要么推出T中存在圈，这都是矛盾！即说明v1与v2是树叶。定理2图G是树当且仅当G中任意两点都被唯一的路连接。证明：“必要性”若不然，设P1与P2是连接u与v的两条不同的路。则(二)、树的性质0.810.60.40.20xt00.511.5210.500.51n11由这两条路的全部或部分将构成一个圈，这与G是树相矛盾。“充分性”首先，因G的任意两点均由唯一路相连，所以G是连通的。其次，若G中存在圈，则在圈中任取点u与v，可得到连接u与v的两条不同的路，与条件矛盾。定理3设T是(n,m)树，则：1mn证明：对n作数学归纳。0.810.60.40.20xt00.511.5210.500.51n12当n=1时，等式显然成立；设n=k时等式成立。考虑n=k+1的树T。由定理1T中至少有两片树叶，设u是T中树叶，考虑T1=T-u,则T1为k阶树，于是m(T1)=k-1,得m(T)=k。这就证明了定理3。例7设T为12条边的树，其顶点度为1,2,5。如果T恰有3个度为2的顶点，那么T有多少片树叶？解：设T有x片树叶。由m=n-1得n=13.于是由握手定理得：1235(10)212xx0.810.60.40.20xt00.511.5210.500.51n13得x=8例8设T为(n,m)树，T中有ni个度为i的点(1≦i≦k),且有：∑ni=n.证明：13422(2)knnnkn证明：由m=n-1得：12()1kmnnn又由握手定理得：1222kmnnkn由上面两等式得：13422(2)knnnkn0.810.60.40.20xt00.511.5210.500.51n14推论1具有k个分支的森林有n-k条边。证明：设森林G的k个分支为Ti(1≦i≦k).对每个分支，使用定理3得：()1,(())iiiimTnnVT所以：1()()kiimGmTnk定理4每个n阶连通图的边数至少为n-1.证明：如果n阶连通图没有一度顶点，那么由握手定理有：()1()()2vVGmGdvn0.810.60.40.20xt00.511.5210.500.51n15如果G有一度顶点。对顶点数作数学归纳。当n=1时，结论显然()1()()2vVGumGudvk设当n=k时，结论成立。当n=k+1时，设u是G的一度顶点，则G-u为具有k个顶点的连通图。若G-u有一度顶点，则由归纳假设，其边数至少k-1,于是G的边数至少有k条；若G-u没有一度顶点，则由握手定理：所以G至少有k+1条边。0.810.60.40.20xt00.511.5210.500.51n16而当G是树时，边数恰为n-1.所以n阶连通图G至少有n-1条边。所以，树也被称为最小连通图。定理5任意树T的两个不邻接顶点之间添加一条边后，可以得到唯一圈。证明：设u与v是树T的任意两个不邻接顶点，由定理2知：有唯一路P连接u与v.于是P∪｛uv｝是一个圈。显然，由P的唯一性也就决定了P∪｛uv｝的唯一性。例9设G是树且Δ≧k,则G至少有k个一度顶点。证明：若不然，设G有n个顶点，至多k-1个一度顶点，由于Δ≧k，于是，由握手定理得：0.810.60.40.20xt00.511.5210.500.51n17所以，有：m(G)n-1,与G是树矛盾！()2()()12()2122vVGmGdvkknknn例10设G是森林且恰有2k个奇数顶点，则在G中有k条边不重合的路P1,P2,…,Pk,使得：12()()()()kEGEPEPEP证明：对k作数学归纳。当k=1时，G只有两个奇数度顶点，此时，容易证明，G是一条路；设当k=t时，结论成立。令k=t+10.810.60.40.20xt00.511.5210.500.51n18在G中一个分支中取两个一度顶点u与v，令P是连接该两个顶点的唯一路，则G-P是有2t个奇数顶点的森林，由归纳假设，它可以分解为t条边不重合的路之并，所以G可以分解为t+1条边不重合的路之并。注：对图作某种形式的分解，是图论的一个研究对象，它在网络结构分析中具有重要作用。例11设T是k阶树。若图G满足δ≧k-1,则T同构于G的某个子图。证明：对k作数学归纳。当k=1时，结论显然。假设对k-1(k≧3)的每颗树T1,以及最小度至少为k-2的每个图H，T1同构于H的某个子图F。现在设T是k阶树，且0.810.60.40.20xt00.511.5210.500.51n19G满足δ(G)≧k-1的图。我们证明T同构于G的某个子图。设u是T的树叶，v是u的邻接顶点。则T-u是k-1阶树。由于δ(G)≧k-1k-2，由归纳假设，T-u同构于G的某个子图F.设v1是与T中v相对应的F中的点，由于dG(v1)≧k-1,所以v1在G中一定有相异于F中的邻点w,作F∪｛v1w｝,则该子图和T同构。v1wFG证明示意图0.810.60.40.20xt00.511.5210.500.51n20树的度序列问题：在第一章中，介绍了判定一个非增非负序列是否为简单图的度序列定理。下面介绍一个判定非增非负序列是否为树的度序列的简单方法。定理6设S=｛d1,d2,…,dn｝是n个正整数序列，它们满足：d1≧d2≧…≧dn,∑di=2(n-1).则存在一颗树T，其度序列为S。证明：对n作数学归纳。当n=1和2时，结论显然。假设对n=k时结论成立。设n=k+10.810.60.40.20xt00.511.5210.500.51n21首先,序列中至少一个数为1，否则，序列和大于2k，与条件相矛盾！所以，dk+1=1.我们从序列中删掉d1和dk+1,增加数d*=d1-1放在它应该在的位置。得到序列S1.该序列含k个数，序列和为2(k-1),由归纳假设，存在树T1，它的度序列为S1.现在，增加结点v，把它和T1中点d*相连得到树T。树T为所求。(三)、树的中心与形心1、树的中心概念与性质0.810.60.40.20xt00.511.5210.500.51n22(1)图的顶点的离心率()max(,)()evduvuVG(2)图的半径()min()()rGevvVG(3)图的直径：最大离心率。(4)图的中心点：离心率等于半径的点。(5)图的中心：中心点的集合。定理7每棵树的中心由一个点或两个相邻点组成。0.810.60.40.20xt00.511.5210.500.51n23对树T的阶数n作归纳证明。当n=1或2时，结论显然成立。设对nk(k≧3)的树结论成立。设T是k阶树。容易知道：删掉T的所有叶，得到的树T1的每个点的离心率比它们在T中离心率减少1。又因T的叶不能是中心点，所以T的中心点在T1中。这样，若点u的离心率在T中最小，则在T1中依然最小，即说明T的中心点是T1的中心点，反之亦然。因为T1的阶数k,所以，由归纳假设，T1的中心为一个点或两个相邻点组成，即证明T的中心由一个点或两个相邻点组成。0.810.60.40.20xt00.511.5210.500.51n24确定图的中心有应用价值。例如，确定社区医院的修建位置，就可以建模成求图的中心问题2、树的形心概念与性质设u是树T的任意一个顶点，树T在顶点u的分支是指包含u作为一个叶点的极大子树，其分支数为顶点u的度数；树T在u点的分支中边的最大数目称为点u的权；树T中权值最小的点称为它的一个形心点。全体形心点的集合称为树T的形心。10984101097810100.810.60.40.20xt00.511.5210.500.51n25定理8每一棵树有一个由一个点或两个邻接的点组成的形心。作业P43习题2：1，2，3，4，5，60.810.60.40.20xt00.511.5210.500.51n26ThankYou!