离散数学图论.pptx

《离散数学图论.pptx》由会员分享，可在线阅读，更多相关《离散数学图论.pptx（120页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、8.1.1 图 现实世界中许多现象能用某种图形表示,这种图形是由一些点和一些连接两点间的连线所组成。【例a，b，c，d 4个篮球队进行友谊比赛。为了表示个队之间比赛的情况，我们作出图的图形。在图中个小圆圈分别表示这个篮球队，称之为结点。如果两队进行过比赛，则在表示该队的两个结点之间用一条线连接起来，称之为边。这样利用一个图形使各队之间的比赛情况一目了然。1.图的定义 8.1 图的基本概念 第1页/共120页 图如果图中的个结点a，b，c，d分别表示个人，当某两个人互相认识时，则将其对应点之间用边连接起来。这时的图又反映了这个人之间的认识关系。8.1 图的基本概念 第2页/共120页 定义一个图

2、G是一个序偶V(G),E(G)，记为GV(G),E(G)。其中V(G)是非空结点集合，E(G)是边集合，对E(G)中的每条边，有V(G)中的结点的有序偶或无序偶与之对应。若边e所对应的结点对是有序偶a,b,则称e是有向边。a叫边e的始点,b叫边e的终点,统称为e的端点。若边e所对应的结点对是无序偶(a,b),则称e是无向边。这时统称e与两个结点a和b互相关联。8.1 图的基本概念 第3页/共120页【例8.1.2】设G=V(G),E(G),其中 V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,e1=(a,b),e2=(a,c),e3=(b,d),e4=(b,c),

3、e5=(d,c),e6=(a,d),e7=(b,b)。则图G可用图8.1.2(a)或(b)表示。我们将结点a、b的无序结点对记为(a，b），有序结点对记为a，b。一个图G可用一个图形来表示且表示是不唯一的。8.1 图的基本概念 第4页/共120页图 8.1.2 8.1 图的基本概念 第5页/共120页2.图G的结点与边之间的关系邻接点:同一条边的两个端点。孤立点:没有边与之关联的结点。邻接边:关联同一个结点的两条边。孤立边:不与任何边相邻接的边。自回路（环）：关联同一个结点的一条边（v，v）或v，v）。平行边(多重边):关联同一对结点的多条边。8.1 图的基本概念 第6页/共120页 如例8.

4、1.1中的图，结点集Va，b，c，d，边集 Ee1，e2，e3，e4，e5，其中 e1（a，b），e2（a,c），e3（a，d），e4（b,c），e5（c,d）。d与a、d与c是邻接的，但d与b不邻接，边e3与e5是邻接的。8.1 图的基本概念 第7页/共120页 【例8.1.3】设图GV,E 如图所示。这里Vv1，v2，v3，Ee1，e2，e3，e4，e5，其中e1=(v1,v2)，e2=(v1，v3)，e3=(v3,v3),e4=(v2,v3),e5=(v2，v3)。在这个图中，e3是关联同一个结点的一条边,即自回路；边e4和e5都与结点v2、v3关联，即它们是平行边。8.1 图的基本概念

5、 图 8.1.3第8页/共120页 3.图G的分类(1)按G的结点个数和边数分为(n,m)图,即n个结点,m条边的图;特别地,(n,0)称为零图,(1,0)图称为平凡图。在零图中边集为空集。(1)(2)按G中关联于同一对结点的边数分为多重图和简单图;(2)多重图:含有平行边的图（如图 8.1.3）；(3)线 图:非多重图称为线图；(4)简单图:不含平行边和自环的图。8.1 图的基本概念 第9页/共120页G1、G2是多重图G3是线图G4是简单图第10页/共120页(3)按G的边有序、无序分为有向图、无向图和混合图;有向图：每条边都是有向边的图称为有向图 （图 8.1.4(b)；无向图：每条边都

6、是无向边的图称为无向图；混合图：既有无向边,又有有向边的图称为混合图。如果将有向图中的每条边都变成无向边，称称为为底底图图(4)按G的边旁有无数量特征分为加权图、无权图(如图 8.1.4);8.1 图的基本概念 第11页/共120页图 8.1.4(5)按G的任意两个结点间是否有边分为完全图Kn(如图和不完全图(如图 8.1.6)。8.1 图的基本概念 第12页/共120页 完全图：任意两个不同的结点都邻接的简单图称为完全图。n 个结点的无向完全图记为Kn。图给出了K3和K4。从图中可以看出K3有条边，K4有条边。容易证明Kn有 条边。8.1 图的基本概念 图 8.1.6图K3与K4示意图第13

7、页/共120页例213213有向完全图无向完全图第14页/共120页 图的结点的度数及其计算 我们常常需要关心图中有多少条边与某一结点关联，这就引出了图的一个重要概念结点的度数。8.1 图的基本概念 定义:在有向图中,以v为终点的边数称为结点v 的入度，记为 ;以v为始点的边数称为结点v 的出度，记为 。结点v的入度与出度之和称为结点v的度数，记为 d(v)或deg(v)。第15页/共120页定义:在无向图中，图中结点v所关联的边数(有环时计算两次)称为结点v 的度数，记为d(v)或deg(v)。第16页/共120页例245136G1顶点2入度：1 出度：3顶点4入度：1 出度：0例15732

8、4G26顶点5的度：3顶点2的度：4第17页/共120页 定理 无向图GV,E中结点度数的总和等于边数的两倍，即证明:因为每条边都与两个结点关联，所以加上一条边就使得各结点度数的和增加 2，由此结论成立。定义：无向图中，如果每个结点的度都是k,则称为k-k-度正则图度正则图。8.1 图的基本概念 第18页/共120页推论:无向图G中度数为奇数的结点必为偶数个。证明:设V1和V2分别是G中奇数度数和偶数度数的结点集。由定理8.1.1知 由于 是偶数之和，必为偶数，而2|E|也为偶数，故 是偶数。由此|V1|必为偶数。8.1 图的基本概念 第19页/共120页 定理 在任何有向图GV,E中，有图第

9、20页/共120页 子图和图的同构 1.子图 在研究和描述图的性质时，子图的概念占有重要地位。定义设有图G=V,E和图 G=V,E 。1)若V V，E E，则称G是G的子图。2)若G是G的子图，且EE，则称G是G 的真子图。第21页/共120页356例245136图与子图第22页/共120页 3)若V=V，E E，则称G是G的生成子图。图给出了图G以及它的真子图G1和生成子图G2。图8.1.7 图G以及其真子图G 1和生成子图G2 8.1 图的基本概念 第23页/共120页给定任意一个含有n个结点的图G,总可以把它补成一个具有同样结点的完全图,方法是把那些缺少的边添上。定义设GV,E是一个具有

10、n个结点的简单图。以V为结点集，以从完全图Kn中删去G的所有边后得到的图（或由G中所有结点和所有能使G成为完全图的添加边组成的图）称为G的补图，记为 。例如，零图和完全图互为补图。8.1 图的基本概念 第24页/共120页G相对于Kn的补图是下图中的第25页/共120页关于补图：1、G与 互为补图第26页/共120页互为补图互为补图互为补图第27页/共120页 1.图的同构 8.1 图的基本概念 试观察下面各图有何异同？第28页/共120页 图同构的图 图 8.1.9 8.1 图的基本概念 第29页/共120页 定义8.1.6 设有图 G=V,E和图G=V,E。如果存在双射：VV，使得 e=(

11、u,v)E e=(u),(v)E，且 (u，v)与(u),(v)有相同的重数，则称G与G 同构。记作GG。注：由同构的定义可知，不仅结点之间要具有一一对应关系，而且要求这种对应关系保持结点间的邻接关系。对于有向图的同构还要求保持边的方向。8.1 图的基本概念 第30页/共120页 【例8.1.5】考察图8.1.9中的两个图GV,E和 G=V,E。显然，定义：VV,(vi)v i,可以验证是满足定义8.1.6的双射，所以GG。8.1 图的基本概念 图 8.1.9第31页/共120页 一般说来，证明两个图是同构的并非是轻而易举的事情，往往需要花些气力。请证明下图中两个图是同构的。第32页/共120

12、页第33页/共120页 根据图的同构定义，可以给出图同构的必要条件如下：(1)结点数目相等；(2)边数相等；(3)度数相同的结点数目相等。(4)有相同重数的边数相同，等等。但这仅仅是必要条件而不是充分条件。第34页/共120页下图中的(a)和(b)满足上述三个条件，然而并不同构。因为在(a)中度数为3的结点x与两个度数为1的结点邻接，而(b)中度数为3的结点y仅与一个度数为1的结点邻接。寻找一种简单有效的方法来判定图的同构，至今仍是图论中悬而未决的重要课题。高等学校高等学校2121世纪教材世纪教材第35页/共120页第36页/共120页 对于同构，形象地说，若图的结点可以任意挪动位置，而边是完

13、全弹性的，只要在不拉断的条件下，这个图可以变形为另一个图，那么这两个图是同构的。故同构的两个图从外形上看可能不一样，但它们的拓扑结构是一样的。第37页/共120页8.2 路与图的连通性(Walks&The Connectivity of Graphs)8.2.1 路 与 回 路(Walks and Circuits)8.2.2 图 的 连 通 性(The Connectivity of Graphs)第38页/共120页路与回路(Wlaks and Circuits)定义 8.2.1 给定图GV,E,设v0,v1,vkV，e1，e2，ekE，其中ei是关联于结点vi-1和vi的边，称交替序列v

14、0e1v1e2ekvk为连接v0到vk的路，v0和vk分别称为路的起点与终点。路中边的数目k称作路的长度。当v0=vk时,这条路称为回路。在简单图中一条路v0e1v1e2ekvk由它的结点序列v0v1vk确定,所以简单图的路,可表示为v0v1vk。如图8.1.1表示的简单图中，路ae1be4ce5d可写成abcd。第39页/共120页 定义 8.2.2 设=v0e1v1e2ekvk是图G中连接v0到vk的路。1)若e1，e2，ek都不相同，则称路为简单路或迹；2)若v0，v1，vk都不相同，则称路为基本路或通路；3)圈中若出现的每条边恰好一次，称简单圈。若出现的每个结点恰好一次，称基本圈。路与

15、回路(Wlaks and Circuits)第40页/共120页结点重复情况结点重复情况边重复情况边重复情况路路 允许允许 允许允许简单路简单路 允许允许不允许不允许 基本路基本路 不允许不允许 不允许不允许 回路回路允许允许允许允许简单圈简单圈允许允许不允许不允许基本圈基本圈不允许不允许不允许不允许路与回路(Wlaks and Circuits)第41页/共120页 例如在图 8.2.1中，有连接v5到v3的路v5e8v4e5v2e6v5e7v3，这也是一条简单路；路 v1e1v2 e3v3是一条基本路；路v1e1v2e3v3e4v2e1v1是一 条回路，但不是基本圈；路v1e1v2e3v3

16、e2v1是一条 简单回路，也是基本圈。图 8.2.1 8.2.1 路与回路(Wlaks and Circuits)第42页/共120页 定义 8.2.3 在图G中，若结点vi到vj有路连接（这时称vi和vj是可达的），其中长度最短的路的长度称为vi到vj 的距离，用符号d(vi,vj)表示。若从vi到vj不存在路径,则d(vi,vj)=。例如在图8.2.1中，（v1，v4）。路与回路(Wlaks and Circuits)第43页/共120页 注意:在有向图中,d(vi,vj)不一定等于d(vj,vi),但一般地满足以下性质:(1)d(vi,vj)0;(2)d(vi,vi)=0;(3)d(vi

17、,vj)+d(vj,vk)d(vi,vk)。图 8.2.1 路与回路(Wlaks and Circuits)第44页/共120页 定理 8.2.1 设G是具有n个结点的图，如果从结点v1到另一结点v2存在一条路，则从结点v1到v2必存在一条长度不大于n1的基本路（通路）。路与回路(Wlaks and Circuits)第45页/共120页 证 明:假 定 从v1到v2存 在 一 条 路 径,(v1,vi,v2)是所经的结点,如果其中有相同的结点vk,例 (v1,vi,vk,vk,v2),则删去从vk到vk的这些边,它仍是从v1到v2的路径,如此反复地进行直至(v1,vi,v2)中没有重复结点为

18、止。此时,所得的就是通路。通路的长度比所经结点数少1,图中共n个结点,故通路长度不超过n-1。推论 设图GV,E，|V|n，则G中任一基本圈长度不大于n。路与回路(Wlaks and Circuits)第46页/共120页 1.无向图的连通性 定义 8.2.4 在无向图如果一个图的任何两个结点之间都有一条路，那么我们称这个图是连通的，否则是不连通的。定义 8.2.5 图G的一个连通的子图G（称为 连通子图）若不包含在G的任何更大的连通子图中，它就被称作G的连通分支。我们把图G的连通分支个数记作（G）。图的连通性(The Connectivity of Graphs)第47页/共120页图 8.

19、2.3 图G与G 在图8.2.3中，G是不连通的，（G），而G是连通的，（G）。任何一个图都可划分为若干个连通分支。显然，仅当图G的连通分支数（G）时，图G是连通的。图的连通性第48页/共120页 在图的研究中，常常需要考虑删去与增加结点、结点集、边和边集（或弧集）的问题。所谓从图G=中删去结点集S，是指作V-S以及从E中删去与S中的全部结点相联结的 边 而 得 到 的 子 图，记 作G-S；特 别 当S=v时，简记为G-v；所谓从图G=中删去边集（或弧集）T，是指作E-T，且T中的全部边所关联的结点仍在V中而得到的子图，记为G-T；特别当T=e 时，简记作G-e。第49页/共120页 所谓图

20、G=增加结点集S，是指作VS以及向E中并入S中、S与V中所成的边而得到的图，记作G+S；特别当S=v 时，简记为G+v；图G=增加边集（或弧集）T是指作ET所得到的图，记作G+T，这里T中全部边（或弧）的关联结点属于V。第50页/共120页 定义:给定连通无向图G=，S V。若(G-S)(G)，但 T S有(G-T)=(G)，则称S是G的一个分离结点集。若图G的分离结点集S=v ，则称v是G的割点。类似地可定义图G的分离边集T；若图G的分离边集T=e ，则称e是G的割边或桥。P122第51页/共120页 对于连通的非平凡图G，称(G)=|S|S是G的分离结点集 为图G的结点连通度，它表明产生不

21、连通图而需要删去结点的最少数目。于是，对于分离图G，(G)=0；对于存在割点的连通图G，(G)=1。第52页/共120页 类似地定义边连通度(G)=|T|T是G的分离边集，它表明产生不连通图而需要删去边的最少数目。可见，对于分离图G，(G)=0；对于平凡图G，(G)=0；对于存在割边的连通图G，(G)=1；对于完全图Kn，(Kn)=n-1。第53页/共120页定理:一个连通无向图G中的边e是割边 存在两个结点u和w，使得联结u与w的每条链都经过e。下面再给出一个判定一条边是割边的充要条件。定理:连通无向图G中的一条边e是割边e不包含在图的任何基本圈中。第54页/共120页 2.有向图的连通性

22、定义8.2.6 在有向图中,若从结点u到v有一条路，则称u可达v。定义8.2.7 设有有向图G，1)若G的任意两个结点中,至少从一个结点可达另一个结点,则称图G是单向连通的;图的连通性第55页/共120页 2)如果G的任意两个结点都是相互可达的,则称图G是强连通的;3)如果略去边的方向后，G成为连通的无向图，则称图G是弱连通的。从定义可知：若图G是单向连通的，则必是弱连通的；若图G是强连通的，则必是单向连通的，且也是弱连通的。但反之不真。第56页/共120页 定义在有向图G=V,E中,G是G的子图,若G是强连通的(单向连通的,弱连通的),但在G中任意增加原图的一些边或一些点，所有子图便不再是强

23、连通的(单向连通的,弱连通的),则称G是G的强分图(单向分图,弱分图)。图的连通性第57页/共120页连通图例245136强连通图356例非连通图连通分图例245136第58页/共120页图图的连通性(The Connectivity of Graphs)第59页/共120页在图8.2.5中,强分图集合是:1,2,3,e1,e2,e3,4,5,6,7,8,e7,e8单向分图集合是:1,2,3,4,5,e1,e2,e3,e4,e5,6,5,e6,7,8,e7,e8 弱分图集合是:1,2,3,4,5,6,e1,e2,e3,e4,e5,e6,7,8,e7,e8图的连通性第60页/共120页下面给出简

24、单有向图的一个应用资源分配图。在多道程序的计算机系统中，可以同时执行多个程序。实际上，程序共享计算机系统中的资源，如磁带机、磁盘设备、CPU、主存贮器和编译程序等。操作系统对这些资源负责分配给各个程序。当一个程序要求使用某种资源，它要发出请求，操作系统必须保证这一请求得到满足。第61页/共120页对资源的请求可能发生冲突。如程序A控制着资源r1，请求资源r2；但程序B控制着资源r2，请求资源r1。这种情况称为处于死锁状态。然而冲突的请求必须解决，资源分配图有助发现和纠正死锁。假设某一程序对一些资源的请求，在该程序运行完之前必须都得到满足。在请求的时间里，被请求的资源是不能利用的，程序控制着可利

25、用的资源，但对不可利用的资源则必须等待。第62页/共120页令Pt=p1，p2，pm 表示计算机系统在时刻t的程序集合，Qt Pt是运行的程序集合，或者说在时刻t至少分配一部分所请求的资源的程序集合。Rt=r1，r2，rn 是系统在时刻t的资源集合。资源分配图Gt=是有向图，它表示了时刻t系统中资源分配状态。把每个资源ri看作图中一个结点，其中i=1，2，n。表示有向边，E当且仅当程序pkQt已分配到资源ri且等待资源rj。第63页/共120页例如，令Rt=r1,r2,r3,r4，Qt=p1,p2,p3,p4。资源分配状态是：p1占用资源r4且请求资源r1；p2占用资源r1且请求资源r2和r3

26、；p3占用资源r2且请求资源r3；p4占用资源r3且请求资源r1和r4。第64页/共120页于是，可得到资源分配图Gt=，如图所示。能够证明，在时刻t计算机系统处于死锁状态资源分配图Gt中包含强分图。于是，对于图，Gt是强连通的，即处于死锁状态。第65页/共120页图第66页/共120页8.3 图的矩阵表示(Matrix Notation of Graph)8.3.1 邻接矩阵(Adjacency Matrices)8.3.2 可达性矩阵(Reachability Matrices)第67页/共120页邻接矩阵(Adjacency Matrices)上面我们介绍了图的一种表示方法，即用图形表示

27、图。它的优点是形象直观，但是这种表示在结点与边的数目很多时是不方便的。下面我们提供另一种用矩阵表示图的方法。利用这种方法，我们能把图用矩阵存储在计算机中，利用矩阵的运算还可以了解到它的一些有关性质。第68页/共120页 定义 8.3.1 设GV,E是有n个结点的简单图，则n阶方阵（aij）称为G的邻接矩阵。其中否则 如图所示的图G，其邻接矩阵A为8.3 图的矩阵表示(Matrix Notation of Graph)第69页/共120页 显然无向图的邻接矩阵必是对称的。下面的定理说明，在邻接矩阵A的幂A2，A3，等矩阵中，每个元素有特定的含义。图8.3.1 G 8.3 图的矩阵表示(Matri

28、x Notation of Graph)第70页/共120页图8.3.1 图G 8.3 图的矩阵表示(Matrix Notation of Graph)第71页/共120页 定理 8.3.1 设G是具有n个结点v1,v2,vn 的图，其邻接矩阵为A，则Ak（k1，2，）的（i，j）项元素a(k)ij是从vi到vj的长度等于k的路的总数。证明:施归纳于k。当k1时，A1A，由A的定义，定理显然成立。若kl时定理成立，则当kl1时，A l+1Al A，所以 8.3 图的矩阵表示(Matrix Notation of Graph)第72页/共120页 根据邻接矩阵定义arj是联结vr和vj的长度为1

29、的路数目,a(l)ir是联结vi和vr的长度为l的路数目,故上式右边的每一项表示由vi经过l条边到vr,再由vr 经过1条边到vj的总长度为l+1的路的数目。对所有r求和,即得a(l+1)ij是所有从vi到vj的长度等于l+1的路的总数,故命题对l+1成立。8.3 图的矩阵表示(Matrix Notation of Graph)第73页/共120页 由定理8.3.1可得出以下结论：1)如果对l1，2，n-1，Al的（i，j）项元素（ij）都为零，那么vi和vj之间无任何路相连接，即vi和vj不连通。因此，vi和vj必属于G的不同的连通分支。8.3 图的矩阵表示(Matrix Notation

30、of Graph)第74页/共120页 2)结点vi 到vj（ij）间的距离d（vi，vj）是使Al（l1，2，n-1）的（i，j）项元素不为零的最小整数l。3)Al的（i，i）项元素a(l)ii表示开始并结束于vi长度为l的回路的数目。8.3 图的矩阵表示(Matrix Notation of Graph)第75页/共120页【例8.3.1】图GV,E的图形如图，求邻接矩阵A和A2，A3，A4，并分析其元素的图论意义。8.3 图的矩阵表示(Matrix Notation of Graph)图 第76页/共120页 解:8.3 图的矩阵表示(Matrix Notation of Graph)第

31、77页/共120页 1)由A中a(1)121知，v1和v2是邻接的；由A3中a(3)122知，v1到v2长度为3的路有两条，从图中可看出是v1v2v1v2和v1v2v3v2。2)由A2的主对角线上元素知，每个结点都有长度为的回路，其中结点v2有两条：v2v1v2和v2v3v2，其余结点只有一条。3)由于A3的主对角线上元素全为零，所以G中没有长度为的回路。8.3 图的矩阵表示(Matrix Notation of Graph)第78页/共120页 4)由于 所以结点v3和v4间无路，它们属于不同的连通分支。5)d（v1，v3）。8.3 图的矩阵表示(Matrix Notation of Gra

32、ph)第79页/共120页8.6 树与生成树(Trees and Spanning Trees)无向树(Undirected Trees)无 向 图 中 的 生 成 树 与 最 小 生 成 树(Spanning Trees and Minimal Spanning Trees)第80页/共120页无向树(Undirected Trees)树是图论中的一个重要概念。早在1847年克希霍夫就用树的理论来研究电网络，1857年凯莱在计算有机化学中2H2n+2的同分异构物数目时也用到了树的理论。而树在计算机科学中应用更为广泛。本节介绍树的基本知识，其中谈到的图都假定是简单图。第81页/共120页 定8

33、.6.1 一个连通无圈无向图称为无向树(简称为树)。记作T。树中度数为1的结点称为树叶（或终端结点），度数大于的结点称为分枝点（或内点，或非终端结点）。一个无圈图称为森林。显然若图G是森林，则G的每个连通分支是树。如图8.6.1(a)所示的是一棵树；(b)所示的是森林。8.6 树与生成树(Trees and Spanning Trees)第82页/共120页图 树和森林示意图 8.6 树与生成树(Trees and Spanning Trees)第83页/共120页【例判断图中各图是否为树.图 8.6 树与生成树(Trees and Spanning Trees)第84页/共120页 证：因为

34、T是一棵n2的（n，m）树，所以由定理，有若T中的无树叶，则T中每个顶点的度数2,则 deg(vi)2n,（2）(1)定理任一树T中,至少有两片树叶(n2时)。8.6 树与生成树(Trees and Spanning Trees)第85页/共120页若T中只有一片树叶，则T中只有一个结点度数为1,其它结点度数2,所以 (3)(2),(3)都与(1)矛盾。所以T中至少有两片树叶。8.6 树与生成树(Trees and Spanning Trees)第86页/共120页 定理一个无向图（n,m）图T是树,当且仅当下列5条之一成立。(或者说,这5条的任一条都可作为树的定义。)(1)无圈且m=n-1。

35、(2)连通且m=n-1。(3)无圈,但增加任一新边,得到且仅得到一个圈。(4)连通但删去任一边,图便不连通(n2)。(5)每一对结点间有唯一的一条通路。(n2)。8.6 树与生成树(Trees and Spanning Trees)第87页/共120页 【例T是一棵树,有两个2度结点，一个3度结点，三个 4度结点，T有几片树叶？解：设树T有x片树叶，则T的结点数 n=2+1+3+x T的边数 m=n-1=5+x 又由 得 2 （5+x）=22+31+43+x 所以x=9，即树T有9片树叶。8.6 树与生成树(Trees and Spanning Trees)第88页/共120页 无向图中的生成

36、树与最小生成树(Spanning Trees and Minimal Spanning Trees)定义 若无向(连通图)G的生成子图是一棵树，则称该树是G的生成树，记为TG。生成树TG中的边称为树枝。图G中其它边称为TG的弦。所有这些弦的集合称为TG的补。如图中(b)、(c)所示的树T1、T2是(a)图的生成树，而(d)所示的树T3不是(a)图的生成树。一般的，图的生成树不唯一。第89页/共120页 图考虑生成树T1，可知e1，e2，e3，e4是T1的树枝，e5，e6，e7是T1的弦，集合e5，e6，e7是T1的补。生成树有其一定的实际意义。8.6 树与生成树(Trees and Spann

37、ing Trees)第90页/共120页 【例某地要兴建5个工厂，拟修筑道路连接这5处。经勘测其道路可依如图a)图的无向边铺设。为使这5处都有道路相通，问至少要铺几条路？解 这实际上是求G的生成树的边数问题。一般情况下，设连通图G有n个结点，m条边。由树的性质知，T有n个结点，n1条树枝，mn1条弦。在图a)中，n5，则n1514，所以至少要修条路才行。8.6 树与生成树(Trees and Spanning Trees)第91页/共120页 定义设G=V,E是一连通的有权图，则G的生成树TG为带权生成树,TG的树枝所带权之和称为。生成树TG的权,记为C(TG)。G中具有最小权的生成树TG称为

38、G的最小生成树。求最小生成树问题是有实际意义的。如要建造一个连接若干城市的铁路网络，已知城市vi和vj之间直达铁路的造价，设计一个总造价为最小的铁路网络，就是求最小生成树TG。下面介绍求TG的克鲁斯克尔（Kruskal)算法。8.6 树与生成树(Trees and Spanning Trees)第92页/共120页 此方法又称为“避圈法”。其要点是，在与已选取的边不成圈的边中选取最小者。具体步骤如下：1)在G中选取最小权边，置边数i1。2)当in1时，结束。否则，转3)。3)设已选择边为 e1,e2,ei，在G中选取不同于e1,e2,ei 的边 ei+1,使 e1,e2,ei,ei+1无圈且e

39、i+1是满足此条件的最小权边。4)置i为i1，转2)。8.6 树与生成树(Trees and Spanning Trees)第93页/共120页 【例求图(0)中有权图的最小生成树。解:因为 图中n8，所以按算法要执行n17次，其过程见图中(1)(7)。8.6 树与生成树(Trees and Spanning Trees)第94页/共120页 图 8.6 树与生成树(Trees and Spanning Trees)第95页/共120页 【例求图中有权图G的最小生成树。解:因为 图中n8，所以按算法要执行n17次。图 8.6 树与生成树(Trees and Spanning Trees)第96

40、页/共120页 【例 图 所 示 的 赋 权 图G表 示 七 个 城 市a,b,c,d,e,f,g及架起城市间直接通讯线路的预测造价。试给出一个设计方案使得各城市间能够通讯且总造价最小,并计算出最小造价。图8.6 树与生成树(Trees and Spanning Trees)第97页/共120页 解:该问题相当于求图的最小生成树问题，此图的最小生成树为图中的TG,因此如图TG架线使各城市间能够通讯，且总造价最小，最小造价为：()8.6 树与生成树(Trees and Spanning Trees)第98页/共120页10.7 根树及其应用(Rooted Trees and Its Applic

41、ations)有向树(directed tree)m叉树(m-ary tree)最优二叉树(optimal binary tree)第99页/共120页有向树(directed tree)图第100页/共120页有向树(directed tree)定义 一个有向图，若不考虑边的方向，它是一棵树，则这个有向图称为有向树。一棵有向树，如果恰有一个结点的入度为，其余所有结点的入度都为，则称为根树，其中入度为的结点称为树根，出度为的结点称为树叶，出度不为的结点称为分枝点或内点。第101页/共120页 如图a)表示一棵根树，其中v1为树根，v1，v2，v3为分枝点，其余结点为树叶。习惯上我们把根树的根画

42、在上方，叶画在下方。这样就可以省去根树的箭头，如图b)。在根树中，称从树根到结点v的距离为该点的层次。这样对图中的根树，v1的层次为，v2、v3的层次为，其余结点的层次均为。我们用家族关系表示根树中各结点的关系。10.7 根树及其应用第102页/共120页图根树示例 10.7 根树及其应用第103页/共120页 定义 在根树中，若从vi到vj可达，则称vi是vj的祖先，vj是vi的后代；又若vi，vj是根树中的有向边，则称vi是vj的父亲，vj是vi的儿子；如果两个结点是同一结点的儿子，则称这两个结点是兄弟。定义 在根树中，任一结点v及其v的所有后代和从v 出发的所有有向路中的边构成的子图称为

43、以v为根的子树。根树中的结点u的子树是以u的儿子为根的子树。10.7 根树及其应用第104页/共120页 在现实的家族关系中，兄弟之间是有大小顺序的，为此我们又引入有序树的概念。定义如果在根树中规定了每一层次上结点的次序，这样的根树称为有序树。我们在有序树中规定同一层次结点的次序是从左至右。10.7 根树及其应用第105页/共120页m叉树(m-ary tree)在树的实际应用中，我们经常研究完全m叉树。定义在根树中，若结点的最大出度等于m，则称这棵树为m叉树。如果每个结点的出度恰好等于或m，则称这棵树为完全m叉树。二叉树(binary tree)的每个结点v 至多有两棵子树，分别称为v的左子

44、树和右子树。第106页/共120页图 第107页/共120页 定理 在完全m叉树中，若树叶数为 t，分枝点数为 i，则 (m-1)it-证明:由假设知，该树有 i+t 个结点，由定理知，该树边数为 i+t-。因为所有结点出度之和等于边数所以根据完全m叉树的定义知，mi i+t-即 (m-1)it-10.7 根树及其应用第108页/共120页 【例假设有一台计算机，它有一条加法指令，可计算 3 个数之和。如果要求 9 个数x1，x2，x9之和，问至少要执行几次加法指令？解:用 3 个结点表示 3 个数，把 9 个数看成树叶，将表示 3 数之和的结点作为它们的父亲结点。这样本问题可理解为求一个完全

45、三叉树的分枝点的个数问题。10.7 根树及其应用第109页/共120页 由定理知，有 (-)i-得 i 所以要执行 4 次加法指令。图表示了两种可能的顺序。10.7 根树及其应用第110页/共120页图 10.7 根树及其应用第111页/共120页 【例设有2828盏灯，拟公用一个电源，则至少需要多少个4插头的接线板?解:把 28盏灯看成树叶，将4插头的接线板看成分枝点,这样本问题可理解为求一个完全四叉树的分枝点的个数 i的问题。由定理知，有 (4-)i28-1 得 i9 所以至少需要9个4插头的接线板。10.7 根树及其应用第112页/共120页 【例 8 枚硬币问题。若有 8 枚硬币a，b

46、，c，d，e，f，g，h，其中 7 枚重量相等，只有 1 枚稍轻。现要求以天平为工具，用最少的比较次数挑出轻币来。解:可用图所示的树表示判断过程。从图中可知，只需称 2 次即可挑出轻币。这种用于描述判断过程的树叫判定树。10.7 根树及其应用第113页/共120页 图 10.7 根树及其应用第114页/共120页 最优二叉树(optimal binary tree)定义设有一棵二叉树，有片树叶。使其树叶分别带权w1，w2，wt的二叉树称为带权的二叉树。定义设有一棵带权w1，w2，wt的二叉树,权为wi的树叶的层为（wi）。1)该带权二叉树的权W（T）定义为 2)在所有带权w1，w2，wt的二叉

47、树中，W(T)最小的树称为最优二叉树。第115页/共120页 1952年哈夫曼给出了求带权w1，w2，wt的最优树的方法:令S=w1，w2，wt，w1w2wt，wi是树叶vi所带的权（i=1，2，t）。（1）在S中选取两个最小的权wi，wj，使它们对应的顶点vi，vj做兄弟，得一分支点vij，令其带权 wij=wi+wj。（2）从S中去掉wi，wj，再加入wij。（3）若S中只有一个元素，则停止，否则转到(1)。10.7 根树及其应用第116页/共120页 【例求带权7，8，9，12，16的最优树。解:全部过程见图a)(d)。10.7 根树及其应用第117页/共120页图第118页/共120页 *7.用dijistra算法求附图中从点a到其它各结点的最短路径，并用图示表示算法中每一次的执行情况。第 7 题 附图 综合练习第119页/共120页感谢您的观看！第120页/共120页