第9章图论.ppt

《第9章图论.ppt》由会员分享，可在线阅读，更多相关《第9章图论.ppt（130页珍藏版）》请在三一办公上搜索。

1、第9章 图 论9.1 图的基本概念9.2 路和回路9.3 连通图9.4 图的矩阵表示9.5 欧拉图和汉密尔顿图9.6 树 9.7 二部图及匹配9.8 平面图,返回总目录,9.1图的基本概念,9.1.1图 两个个体x，y的无序序列称为无序对，记为(x,y)。在无序对(x,y)中，x，y是无序的，它们的顺序可以颠倒，即(x,y)=(y,x)。定义9.1.1 图G是一个三重组V(G),E(G),G 其中：V(G)是非空结点集。E(G)是边集。G是边集到结点的有序对或 无序对集合的函数。,【例9.1】G=V(G),E(G),G 其中：V(G)=a,b,c,d E(G)=e1,e2,e3,e4 G：G(

2、e1)=(a,b)G(e2)=(b,c)G(e3)=(a,c)G(e4)=(a,a)试画出G的图形。解：G的图形如图9.1所示。,由于在不引起混乱的情况下，图的边可以用有序对或无序对直接表示。因此，图可以简单的表示为：G=V,E 其中：V是非空的结点集。E是边的有序对或无序对组成的集合。按照这种表示法，例9.1中的图可以简记为：G=V,E 其中：V=a,b,c,d E=(a,b),(b,c),(a,c),(a,a),定义9.1.2 若图G有n个结点，则称该图为n阶图。定义9.1.3 设G为图，如果G的所有边都是有向边，则称G为有向图。如果G的所有边都是无向边，则称G为无向图。如果G中既有有向边

3、，又有无向边，则称G为混合图。图9.3的(a)是无向图，(b)是有向图，(c)是混合图。,在一个图中，若两个结点由一条边(有向边或无向边)关联，则称其中的一个结点是另一个结点的邻接点。并称这两个结点相互邻接。在一个图中不与任何结点相邻接的结点，称为孤立点。在一个图中，如果两条边关联于同一个结点，则称其中的一个边是另一个边的邻接边。并称这两个边相互邻接。关联于同一个结点的一条边叫做环或自回路。在有向图中环的方向可以是顺时针，也可以是逆时针，它们是等效的。定义9.1.4 由孤立点组成的图叫做零图。由一个孤立点组成的图叫做平凡图。根据定义9.1.4，平凡图一定是零图。,9.1.2结点的度及其性质 定

4、义9.1.5 设G=V,E是图，vV，与v相关联的边数叫做结点v的度。记为deg(v)。规定，自回路为所在结点增加2度。在图G=V,E中，度数最大(小)的结点的度叫做图G的最大(小)度，记为(G)(G)。图G的最大度和最小度表示为：(G)=max deg(v)|vV(G)=min deg(v)|vV 在图9.1中，(G)=4，(G)=0。,定理9.1.1 在任何图G=V,E中，所有结点度数的和等于边数的2倍。即：=2|E|证明：图的每一条边都和两个结点相关联，为每个相关联的结点增加一度,给图增加两度。所以所有结点度数的和等于边数的2倍。推论 在任何图G=V,E中，度数为奇数的结点必为偶数个。,

5、定义9.1.6 设G=V,E是有向图，vV，射入(出)结点v的边数称为结点v的入(出)度。记为deg(v)(deg(v)。显然，任何结点的入度与出度的和等于该结点的度数，即deg(v)=deg(v)+deg(v)。定理9.1.2 在有向图中，所有结点入度的和等于所有结点出度的和。证明：在有向图中每一条边对应一个入度和一个出度，为图的入度和出度各增加1。所以，所有结点入度的和等于边数，所有结点出度的和也等于边数。,9.1.3多重图、简单图、完全图和正则图 定义9.1.7 在图G中，连接同一对结点的多条相同边称为平行边。平行边的条数称为该平行边的重数。含平行边的图叫多重图。不含平行边和环的图叫简单

6、图。,定理9.1.3 设G为n阶简单无向图，则(G)n1。证明：因为G有n个结点，G的任何结点v最多只能与其余的n1结点相邻接；又因为G为简单图，既无平行边，又无环。所以deg(v)n1。由v的任意性，就有(G)=maxdeg(v)|vVn1。定义9.1.8 设G为n阶简单无向图，若G中的每个结点都与其余的n1个结点相邻接，则称G为n阶无向完全图。记为Kn。在n阶无向完全图中，给每一条边任意确定一个方向，所得到的图称为n阶有向完全图。也记为Kn。今后，将n阶无向完全图和n阶有向完全图统称为n阶完全图。,定理9.1.4 n阶完全图Kn的边数为 证明：在Kn中，每个结点都与其余的n1结点相邻接，即

7、任何一对结点之间都有一条边，故边数应为 定义9.1.9 设G为n阶简单无向图，若G中每个结点都是k度的，则称G为k次正则图。,9.1.4图的同构 在图论中只关心结点间是否有连线，而不关心结点的位置和连线的形状。因此，对于给定的图而言，如果将图的各结点安排在不同的位置上，并且用不同形状的弧线或直线表示各边，则可以得到各种不同图形。所以，同一图的图形并不惟一。由于这种图形表示的任意性，可能出现这样的情况：看起来完全不同的两种图形，却表示着同一个图。例如，在图9.6中，(a)和(b)两个图的图形不同，但它们的结构完全相同，是同一个图。为了描述看起来不同，而其结构完全相同的图，引入了同构的概念。,两个

8、图同构必须满足下列条件：结点数相同。边数相同。度数相同的结点数相同。这三个条件是两个图同构的必要条件，不是充分条件。一般的，用上述三个必要条件判断两个图是不同构的。,定义9.1.12 设G=V,E与G1=V1,E1是两个图。如果V1V且E1E，则称G1是G的子图，G是G1的母图；如果V1V且E1E，则称G1是G的真子图；如果V1V且E1E则称G1是G的生成子图。,在图9.10中，(b)是(a)的子图、真子图、生成子图。,返回章目录,9.2 路和回路,定义9.2.1 设G=V,E是图，G中的结点与边的交替序列L：v0e1v1e2v2envn叫做v0到vn的路。其中vi-1与vi是ei的端点，i=

9、1,n。v0和vn分别叫做路L的始点和终点。路L中边的条数叫做该路的长度。例如，在图9.11中，L1：v5e8v4e5v2e6v5e7v3 是从v5到v3的路，v5是始点，v3是终点，长度为4。L2：v1e1v2e3v3 是从v1到v3的路，v1是始点，v3是终点，长度为2。在简单图中没有平行边和环，路L：v0e1v1e2v2envn完全由它的结点序列v0v1v2 vn确定。所以，在简单图中的路可以用结点序列表示。,定义9.2.2 设G=V,E是图，L是从 v0到vn的路。若v0=vn，则称L为回路。若L中所有边各异，则称L为简单路。若此时又有v0=vn，则称L为简单回路。若L中所有结点各异，

10、则称L为基本路。若此时又有v0=vn，则称L为基本回路。若L既是简单路，又是基本路，则称L为初级路。若此时又有v0=vn，则称L为初级回路。在图9.11中，L1是一条简单路。L2是一条简单路、基本路、初级路。,定理9.2.1 在n阶图G中，若从结点vi到vj(vivj)存在一条路，则必存在长度小于等于n-1的路 推论 在n阶图G中，若从结点vi到vj(vivj)存在路，则必存在长度小于等于n-1的初级路。定理9.2.2 在n阶图G中，若存在结点vi到自身的回路，则必存在vi到自身长度小于等于n的回路。推论 在n阶图G中，若存在结点vi到自身的简单回路，则必存在vi到自身长度小于等于n的初级回路

11、。,返回章目录,9.3连通图,9.3.1无向连通图 定义9.3.1 在无向图G中，如果结点u和结点v之间存在一条路，则称结点u和结点v连通。记为uv。规定，G中任意结点v和自身连通，即vv。在无向图中，如果结点u和结点v连通，即uv，那么，结点v和结点u连通，即vu。所以，无向图结点间的连通是对称的。设G=V,E是无向图，在图G的结点集V上建立一个二元关系R：R=u,v|uVvVu和v连通 R叫做无向图G的结点集V上的连通关系。因为R是自反的、对称的、传递的，所以R是V上的等价关系。无向图G的结点集V上的连通关系是等价关系。,设G是图9.14。结点集V上的连通关系为R，以下验证R是V上的等价关

12、系，并找出所有等价类。R=a,a,a,b,a,c,b,a,b,b,b,c,c,a,c,b,c,c,d,d,e,e,e,f,e,g,e,h,f,e,f,f,f,g,f,h,g,e,g,f,g,g,g,h,h,e,h,f,h,g,h,h=a,b,ca,b,cdde,f,g,he,f,g,h,根据定义，R是V上的等价关系。等价类有三个，分别是：a,b,c，d，e,f,g,h。,定义9.3.2 若无向图G中的任何两个结点都是连通的，则称G为连通图。规定，平凡图(一个孤立点）是连通图。定义9.3.3 设G=V,E是图 V1V且V1，E1是G中两个端点都在V1中的边组成的集合，图G1=V1,E1叫做G的由

13、V1导出的子图，记为GV1。E2E且E2，V2是由E2中的边所关联的结点组成的集合，图G2=V2,E2叫做G的由E2导出的子图，记为GE2。,在图9.15中，设图G为(a)，取V1=a,b,c，则G的由V1导出的子图GV1是(b)。取E2=(a,b),(d,c)，G的由E2导出的子图GE2是(c)。,定义9.3.4 设G=V,E是无向图，R是V上的连通关系，V/R=ViVi是R的等价类，i=1,k 是V关于R的商集，GVi是Vi导出的子图，称GVi(i=1,k)为G的连通分支。G的连通分支数记为W(G)。设图9.14为G，在G中，连通关系R的三个等价类是a,b,c，d，e,f,g,h，它们导出

14、的G的子图分别是图9.14中的(a)，(b)，(c)。它们都是G的连通分支。G的连通分支数W(G)=3。每一个连通分支都是原图的最大的连通子图。,定义9.3.5 设u，v是无向图G中的任意两个结点，若u和v连通，则u和v之间最短路的长叫做结点u与结点v的距离，记为d(u,v)。若u和v不连通，规定，u与v的距离为。即d(u,v)=。设G=V,E是无向图，u、v和w是V中的任意结点，G的结点间的距离有以下的性质：d(u,v)0 d(u,u)=0 d(u,v)d(v,w)d(u,w)d(u,v)=d(v,u)在n阶无向完全图Kn中，每两个不同结点间都有一条边，它们的距离是1。在零图中，每两个不同结

15、点间都没有路，它们的距离都是。在图G中删除一个结点，就是将这个结点与它的所有关联边全部删除。删除一个边，则仅去掉这个边。,定义9.3.6 设G=V,E是无向连通图，V1V且V1，满足：删除V1的所有结点，得到的子图是不连通的。删除V1的任何真子集，得到的子图是连通的。则称V1是G的点割集。如果某一个结点组成了点割集，则称该点为割点。,在图9.16中，b,d，c，e都是点割集，结点c和结点e都是割点。虽然删除结点a和c图成为不连通的，但因c是a,c的真子集，所以a,c不是点割集。,定义9.3.7 设G=V,E是无向连通图，如果G不是完全图，k(G)=min|V1|V1是G的点割集称为图G的点连通

16、度。如果G是完全图，规定n阶无向完全图Kn的点连通度为n1，即k(Kn)=n1。规定不连通图G的点连通度为0。即k(G)=0。图9.16是无向连通图，但不是完全图，存在割点c和e，所以点连通度是1。无向连通图的点连通度的物理意义是：要使G成为不连通的最少要删除的结点数。图9.16的点连通度是1，最少删除一个结点，图成为不连通的，例如删除结点c或结点e。,定义9.3.8 设G=V,E是无向连通图，E1E且E1，满足：删除E1的所有边，得到的子图是不连通的。删除E1的任何真子集，得到的子图是连通的。则称E1是G的边割集。如果某一条边组成了边割集，则称该边为割边或桥。在图9.16中，集合(c,e)、

17、(e,f)、(a,b),(d,c)和(a,d),(b,c)都是G的边割集，无向边(c,e)和(e,f)为割边。虽然删除边(a,d)、(a,b)和(d,c)图成为不连通的，但因集合(a,b),(d,c)是集合(a,d),(a,b),(d,c)的真子集，所以(a,d),(a,b),(d,c)不是边割集。,定义9.3.9 设G=V,E是无向连通图，如果G是非平凡图，(G)=min|E1|E1是G的边割集称为G的边连通度。如果G是平凡图，规定G的边连通度为0。规定不连通图G的边连通度为0，即(G)=0。图9.16是无向连通图，但不是平凡图，存在割边(c,e)和(e,f)，所以，它的边连通度是1。无向连

18、通图的边连通度的物理意义是：要使G成为不连通的最少要删除的边数。图9.16的边连通度是1，最少删除一条边，图就会成为不连通的，例如删除割边(c,e)或(e,f)。无向图G的点连通度k(G)、边连通度(G)和最小度(G)有下列的关系：,定理9.3.1 设G=V,E为任意无向图，则k(G)(G)(G)图9.17是无向连通图，点连通度k(G)=1，边连通度(G)=2，最小度(G)=3，此图满足k(G)(G)(G)。,9.3.2有向连通图 定义9.3.10 在有向图G中，结点u到结点v存在一条路，则称结点u到结点v可达。记为uv。规定，G中任何结点v自己到自己可达，即vv。定义9.3.11 在有向图G

19、=V,E中，uV，vV，若结点u到结点v可达，u到v最短路的长称为结点u到结点v的距离。记为du,v。若u到v不可达，即du,v=。对于有向图G中的任意结点u,v和w，结点间的距离有以下的性质：du,v0 du,u=0 du,vdv,wdu,w,定义9.3.12 在简单有向图G中，对于任意两个结点u和v，如果结点u到结点v可达或结点v到结点u可达，则称G为单向(侧)连通的。如果结点u和结点v互相可达，则称G为强连通的。如果略去方向得到的无向图是连通的，则称G为弱连通的。在图9.18中，(a)是强连通的、单向(侧)连通的和弱连通的。(b)是单向(侧)连通的和弱连通的，但不是强连通的。(c)是弱连

20、通的，但不是单向(侧)连通的，也不是强连通的。,一般地说，若有向图G是强连通的，则必是单向(侧)连通的和弱连通的；若有向图G是单向(侧)连通的，则必是弱连通的。反之不真。,是弱连通的,单向(侧)连通的和弱连通,是强连通的,定理9.3.3 一个有向图G是强连通的充分必要条件是G中有一个回路至少包含G的每个结点一次。定理9.3.4 一个有向图G是单向连通的充分必要条件是G中有一个路至少包含每个结点一次。,定义9.3.13 在简单有向图G中，具有强(单向，弱)连通性质的最大子图叫做强(单向，弱)分图。在图9.19(a)中，由v1,v2,v3,v4导出的子图是强分图，v5导出的子图也是强分图。由v1,

21、v2,v3,v4,v5导出的子图是单向分图，也是弱分图。在图9.19(b)中，v1，v2，v3，v4导出的子图是强分图，v1,v2,v3，和v1,v3,v4导出的子图是单向分图，v1,v2,v3,v4导出了弱分图。,例如图9.22的邻接矩阵为：,又如图9.23(a)的邻接矩阵为：,邻接矩阵具有以下性质：邻接矩阵的元素全是0或1。这样的矩阵叫布尔矩阵。无向图的邻接矩阵是对称阵，有向图的邻接矩阵不一定是对称阵。邻接矩阵与结点在图中标定次序有关。,。对有向图来说，邻接矩阵A(G)的第i行1的个数是vi的出度，第j列1的个数是vj的入度。零图的邻接矩阵的元素全为零，叫做零矩阵。反过来，如果一个图的邻接

22、矩阵是零矩阵，则此图一定是零图。,定理9.4.1 设A(G)是图G的邻接矩阵，A(G)k=A(G)A(G)k-1，A(G)k的第i行，第j列元素 等于从vi到vj长度为k的路的条数。其中 为vi到自身长度为k的回路数。推论 设G=V,E是n阶简单有向图，A是有向图G的邻接矩阵，Bk=AA2Ak，Bk=()nn，则 是G中由vi到vj长度小于等于k的路的条数。是G中长度小于等于k的路的总条数。是G中长度小于等于k的回路数。【例9.4】设G=V,E为简单有向图，图形如图9.24，写出G的邻接矩阵A，算出A2，A3，A4且确定v1到v2有多少条长度为3的路?v1到v3有多少条长度为2的路?v2到自身

23、长度为3和长度为4的回路各多少条?,解：邻接矩阵A和A2，A3，A4如下：,=2，所以v1到v2长度为3的路有2条，它们分别是：v1v2v1v2和v1v2v3v2。=1，所以v1到v3长度为2的路有1条：v1v2v3。=0，v2到自身无长度为3的回路。=4，v2到自身有4条长度为4的回路，它们分别是：v2v1v2v1v2、v2v3v2v3v2、v2v3v2v1v2和v2v1v2v3v2。,定义9.4.2 设G=V,E是简单有向图，V=v1,v2,vn P(G)=(pij)nn 其中：pij=i,j=1,n称P(G)为G的可达性矩阵。简记为P。在定义9.3.10中，规定了有向图的任何结点自己和自

24、己可达。所以可达性矩阵P(G)的主对角线元素全为1。,使用上述方法，计算例9.4中图G的可达性矩阵，,C4=A0AA2A3A4=,P=,计算简单有向图G的可达性矩阵P，还可以用下述方法：设A是G的邻接矩阵，令A=(aij)nn，A(k)=()nn，A0为n阶单位阵。A(2)=AA，其中=(ai1a1j)(ai2a2j)(ainanj)i,j=1,n。A(3)=AA(2)，其中(ai1)(ain)i,j=1,n。P=A0AA(2)A(3)A(n1)。其中，运算是矩阵对应元素的析取。可达性矩阵用来描述有向图的一个结点到另一个结点是否有路，即是否可达。无向图也可以用矩阵描述一个结点到另一个结点是否有

25、路。在无向图中，如果结点之间有路，称这两个结点连通，不叫可达。所以把描述一个结点到另一个结点是否有路的矩阵叫连通矩阵，而不叫可达性矩阵。,定义9.4.3 设G=V,E是简单无向图，V=v1,v2,vn P(G)=(pij)nn 其中：i,j=1,n称P(G)为G的连通矩阵。简记为P。无向图的邻接矩阵是对称阵，无向图的连通矩阵也是对称阵。求连通矩阵的方法与可达性矩阵类似。,定义9.4.4 设G=V,E是无向图，V=v1,v2,vp，E=e1,e2,eq M(G)=(mij)pq 其中：i=1,p，j=1,q称M(G)为无向图G的完全关联矩阵。简记为M。,设G=V,E是无向图，G的完全关联矩阵M(

26、G)有以下的性质：每列元素之和均为2。这说明每条边关联两个结点。每行元素之和是对应结点的度数。所有元素之和是图各结点度数的和，也是边数的2倍。两列相同，则对应的两个边是平行边。某行元素全为零，则对应结点为孤立点。定义9.4.5 设G=V,E是有向图，V=v1,v2,vp，E=e1,e2,eq M(G)=(mij)pq 其中：i=1,p，j=1,q 称M(G)为有向图G的完全关联矩阵。简记为M。,图9.26的完全关联矩阵为：,M(G)=,设G=V,E是有向图，G的完全关联矩阵M(G)有以下的性质：每列有一个1和一个-1，这说明每条有向边有一个始点和一个终点。每行1的个数是对应结点的出度，-1的个

27、数是对应结点的入度。所有元素之和是0，这说明所有结点出度的和等于所有结点入度的和。两列相同，则对应的两边是平行边。,返回章目录,9.5欧拉图和汉密尔顿图 9.5.1欧拉图 定义9.5.1 在无孤立结点的图G(有向图或无向图)中，如果存在一条路经过每一条边一次且仅一次，则称该路为欧拉路。如果存在一条回路经过每一条边一次且仅一次，则称该回路为欧拉回路。具有欧拉回路的图称为欧拉图。定理9.5.1 无向图G具有一条欧拉路当且仅当G是连通的且有零个或两个奇度结点。推论 无向图G具有一条欧拉回路当且仅当G是连通的且所有结点都是偶度的,图9.30(a)的每一个结点的度数都是偶数2，所以(a)中有一个欧拉回路

28、，是欧拉图；在图9.30(b)中有两个结点的度数是奇数3，故(b)中有一个欧拉路，但没有欧拉回路，不是欧拉图；在图9.30(c)中四个结点的度数都是奇数3，(c)中没有欧拉路，更没有欧拉回路，不是欧拉图。,定理9.5.2 有向图G具有一条欧拉回路当且仅当G是强连通的且每个结点的入度等于出度。定理9.5.3 有向图G具有一条欧拉路当且仅当G是单向连通的且除了两个结点外，每个结点的入度等于出度，而在这两个结点中，一个结点入度比出度大1，另一个结点入度比出度小1。,图9.31(a)是强连通的且每一个结点的入度等于出度，都等于1，所以(a)中有一个欧拉回路，是欧拉图；图9.31(b)是单向连通的且有两

29、个结点入度与出度相等，有两个结点入度与出度不相等，其中一个结点入度比出度大1，另一个结点入度比出度小1。故有一个欧拉路，但没有欧拉回路，不是欧拉图；图9.31(c)的四个结点入度与出度都不相等，没有欧拉路，更没有欧拉回路。,哥尼斯堡七桥问题,9.5.2汉密尔顿图 一个与欧拉回路和欧拉图非常类似的问题是汉密尔顿回路和汉密尔顿图问题。它是由爱尔兰数学家威廉汉密尔顿爵士(Sir Willian Hamilton)于1859首先提出的。定义9.5.2 在图G(有向图或无向图)中，如果存在一条路，经过每个结点一次且仅一次，则该路称为汉密尔顿路。如果存在一条回路，经过每个结点一次且仅一次，则称该路为汉密尔

30、顿回路。具有汉密尔顿回路的图称为汉密尔顿图。与欧拉图不同，判断一个图是否为汉密尔顿图至今还没有一个简单的充分必要条件，只有一些必要条件和充分条件。判断一个图是汉密尔顿图的充分必要条件是图论中尚未解决的基本难题之一。,先给出一个约定：设G=V,E是图，SV，用G-S表示从图G中删除S中的所有结点所得的子图。定理9.5.4 设无向图G=V,E是汉密尔顿图，S是V的任意非空子集，则W(G-S)|S|。证明：设C是G的一条汉密尔顿回路，v1S，则C-v1(从C中删除结点v1)是一条路或回路，路上各结点相互连通。再删除S中的另一个结点v2，则W(C-v1,v2)2，所以W(C-v1,v2)|v1,v2|

31、。由归纳法可得W(C-S)|S|。又因为C-S是G-S的生成子图，因而 W(GS)W(CS)，所以有W(GS)|S|。本定理的条件是汉密尔顿图的必要条件，而不是充分条件。利用该定理可以证明一个图不是汉密尔顿图，即满足此定理条件的图不一定是汉密尔顿图，而不满足此定理条件的图一定不是汉密尔顿图。,例如，图9.34叫彼得松图。彼得松图满足定理9.5.4的条件，但可以验证它不是汉密尔顿图。又如，在图9.35中，|图不是汉密尔顿图。,【例9.5】设G是无向连通图，证明：如果G中有割点或桥，则G一定不是汉密尔顿图。证明：设v是割点。删除结点v，图成为不连通的，且至少有两个连通分支。令S=v，则W(GS)2

32、1=|S|，即W(GS)|S|。依据定理9.5.4，G不是汉密尔顿图。如果G中有桥，则该桥的一个端点是割点。可以归结为G中有割点的情况。所以G也不是汉密尔顿图。定理9.5.5 设G=V,E是n阶无向简单图，如果G中每一对结点度数的和大于等于n1，则在G中存在一条汉密尔顿路。推论 设G=V,E是n阶无向简单图，如果G中每一对结点度数的和大于等于n，则在G中存在一条汉密尔顿回路。,定理9.5.5及其推论给出了图中存在一条汉密尔顿路和汉密尔顿回路的充分条件，而不是必要条件。例如，图9.37(a)有6个结点，任意两个结点度数的和小于5，但图中存在一条汉密尔顿路。又如图图9.37(b)也有6个结点，任意

33、两个结点度数的和小于6，但图中存在一条汉密尔顿回路。,【例9.6】设G=V,E是一个无向简单图，|V|=n，|E|=m，设m(n1)(n2)。试证明G中存在一条汉密尔顿路。证明：先证明图G中，然后利用定理9.5.5即得本例要证的结果。用反证法，设图G中存在两个结点v1和v2，使得deg(v1)deg(v2)n1，即deg(v1)deg(v2)n2。删去结点v1和v2后，得到图G，G是具有n-2个结点的无向简单图。设G的边数为m,则mm-(n-2)(n-1)(n-2)-(n-2)=(n-2)(n-3)，即m(n2)(n3)另一方面，G是具有n2个结点的无向简单图，它最多有(n2)(n3)条边。所

34、以m(n2)(n3)。由此得出矛盾。所以deg(v1)deg(v2)n1，由定理9.5.5得G中存在一条汉密尔顿路。,【例9.7】某地有5个风景点，若每个风景点均有两条道路与其它点相通，问是否可经过每个风景点恰好一次的游完这5处?解：因为有5个风景点，故可看成一个有5个结点的无向图，其中每处均有两条路与其它结点相通，所以deg(vi)=2，i=1,5。故对任意两点vi，vj均有 deg(vi)+deg(vj)=2+2=4=5-1 由定理9.5.5可知此图中一定有一条汉密尔顿路，本题有解。定义9.5.3 给定图G=V,E有n个结点，若将图G中度数之和至少是n的非邻接结点连接起来得图G，对图G重复

35、上述步骤，直到不再有这样的结点对存在为止，所得到的图称为原图G的闭包，记作C(G)。,任意两个不同的结点度数之和大于等于n-1,例如图9.38给出了有六个结点的图G构造其闭包的过程。在这个例子中C(G)是完全图。一般情况下，C(G)也可能不是完全图。,将图G中度数之和至少是n的非邻接结点连接起来得图G定理9.5.6 设G是简单图,G是汉密尔顿图当且仅当G的闭包是汉密尔顿图。,下面通过一个例子，介绍一个判别汉密尔顿路不存在的方法。【例9.8】图G如图9.39所示，证明G中没有汉密尔顿路。证明：任取一结点a用A标记，所有与它相邻接的结点标记为B。再用A标记所有邻接于B的结点，继续用B标记所有邻接于

36、A的结点，直到所有的结点标记完毕。如果图中有一条汉密尔顿路，那么它必交替通过标记A的结点和标记B的结点，故或者标记A的结点与标记B的结点数一样，或者两者相差为1。然而本例有3个结点标记A，5个结点标记B，它们相差为2，所以该图不存在汉密尔顿路。,返回章目录,9.6 树 9.6.1无向树 定义9.6.1 连通无回路的无向图称为无向树，简称树。常用T表示。在树中，度数为1的结点称为树叶，度数大于1的结点称为分支点或内点。规定，平凡图也是树，叫平凡树。定义9.6.2 若无向图至少有两个连通分支，每一个连通分支是树，则此无向图称为森林。,定理9.6.1 设G=V,E是无向图，|V|=n，|E|=m，则

37、下列各命题是等价的：G是树。G中每一对结点之间存在惟一的路。G中无回路且m=n1 G是连通的且m=n1 G是连通的且G中任何边均为桥。G中无回路，但在任何两个不同的结点之间增加一个新边，得到一个惟一的含新边的回路。,定理9.6.2 在任何n阶非平凡的无向树T中至少有两片树叶。,9.6.2生成树 定义9.6.3 设G为无向图，若G的生成子图是一棵树，则该树称为G的生成树。设G的生成树为T，则T中的边称为树枝。在图9.40中，(b)是(a)的生成树，(c)是(a)的生成树，,定理9.6.3 无向图G具有生成树的充分必要条件是G为连通图。,推论1 无向连通图G有n个结点和m条边，则 mn1 推论2

38、在无向连通图中，一个回路和任何一棵生成树的补至少有一条公共边。推论3 在无向连通图中，一个边割集和任何一棵生成树至少有一条公共边。,定义9.6.4 设G为无向连通图，有n个结点和m条边。要得到一棵生成树，必须删除G的mn1条边。mn1称为无向连通图G的秩。无向连通图的秩，与生成树的选择无关。定义9.6.5 设G=V,E为无向连通图，eE，对边e指定一个正数C(e)，称正数C(e)为边e的权。设T是G的生成树，T的所有边e的权之和称为树T的权。记为C(T)。若G的每一条边都指定权，则称G为赋权图。在实际应用中，边的权可以是长度，运输量或其它费用。,定义9.6.6 在图G的所有生成树中，权最小的生

39、成树，称为最小生成树。定理9.6.4 设G=V,E为无向连通赋权图，|E|=m，以下算法可以产生最小生成树T：先将图的m条边按它的权由小到大的顺序排列为：e1,e2,em。取e1到T中。在尚未检查过的边中从左到右依次检查，若ej与T中的边不能构成回路，则取ej到T中，否则跳过。反复做，直到所有边都已检查。,定理9.6.4描述的算法叫克鲁斯克尔(kruskal)算法。【例9.8】图9.41(a)给出了一个赋权图G，用kruskal算法求出G的最小生成树。解：先将m条边按权由小到大排列：(v4,v5)，(v1,v8)，(v5,v7)，(v6,v7)，(v4,v6)，(v5,v6)，(v2,v7)，

40、(v2,v5)，(v7,v8)，(v2,v3)，(v3,v4)，(v1,v2)。它们的权分别是：3，4，5，6，6.5，7，7.5，8，10.5，11，12，13。逐次取边：(v4,v5)，(v1,v8)，(v5,v7)，(v6,v7)，(v2,v7)，(v7,v8)，(v2,v3)，构成的生成树在图9.41(b)，这是G的最小生成树。最小生成树T的权C(T)=3+4+5+6+7.5+10.5+11=47。,9.6.3根树及其应用 定义9.6.7 一个有向图，略去方向后是树，则称这个有向图为有向树。如果一棵有向树恰有一个结点入度为0，其余所有结点入度为1，此有向树称为根树。在根树中，入度为0的

41、结点称为树根，出度为0的结点称为树叶，出度不为0的结点称为分枝点或内点。从此定义可以看出，在根树中，除了树叶都是分枝点或内点外，树根也是分枝点。9.42(a)是一棵有向树。(b)是一棵根树。v1是树根，v3,v5,v6,v8是树叶，v1,v2,v4,v7是分枝点。,有向树,根树,定义9.6.8设T是一棵根树，由树根到T的任意结点v的路长叫做结点v的层数。层数最大的结点的层数叫做该树的高。在根树中，各有向边的方向是一致的。所以画根树时，可以省略各边的方向，并且常将树根画在最上方。定义9.6.9 在根树中，若vi到vj有一条路，则称vi是vj的祖先，vj是vi的后代。若vi,vj是根树中的一条边，

42、则称vi是vj的父亲，vj是vi的儿子；同一个分枝点的儿子叫兄弟。定义9.6.10 设T是一棵根树，将T中层数相同的结点标定一个次序，则称T为有序树。定义9.6.11 设T是一棵根树，v是T的任意结点，把v和它的所有后代组成的结点集导出的图叫做T的以v为根的根子树，简称为以v为根的子树，记为Tv。,定义9.6.12 在根树中，若每个结点的出度小于或等于m，则称该树为m叉树。在m叉树中，若每个结点的出度恰等于0或m，则称该树为完全m叉树。在完全m叉树中，若所有树叶层数相同，则称该树为正则m叉树。二叉树的每一个结点v至多有两棵根子树，分别称为v的左子树和右子树。一般的，左子树画在v的左下方，右子树

43、画在v的右下方。二叉树的每一个结点v至多有两个儿子，左边的叫左儿子，右边的叫右儿子。,正则二叉树,完全二叉树,二叉树,定理9.6.5 在完全m叉树中，其树叶数为t，分枝点数为i，则(m-1)i=t-1。证明：由定理的条件知，该树有it个结点，由定理9.6.1知，该树边数为it-1。另一方面，由完全m叉树定义知，该树出度的和为：mi，这也是该树的边数，于是有mi=it-1。整理后有(m-1)i=t-1。【例9.10】设有一台计算机，它有一条加法指令，可计算3个数的和。如果要计算9个数的和，问至少要执行几次加法指令？解：用3个结点表示三个数，用它们的父结点表示它们的和。于是，问题就抽象为求一个完全

44、3叉树的分枝点有多少个。把9看成树叶的个数，依据定理9.6.5，(3-1)i=9-1，i=4。所以要执行4次加法指令。,任何一棵有序根树都可用二叉树来表示，其方法如下：从根结点开始，保留父亲和最左边儿子的连线，取消和其他儿子的连线，兄弟之间用从左到右的有向边连接。选定二叉树的左儿子和右儿子如下：处于给定结点下方的结点作为该结点的左儿子，同一水平线上与给定结点右邻的结点作为该结点的右儿子。图9.44(a)是一棵有序根树，做完得(b)，做完得(c)，(c)是一颗二叉树。,图9.45的(a)也是一棵有序根树，按照上述方法，做完得(b)，做完得(c)，(c)是一颗二叉树。,定义9.6.14 设T是一棵

45、二叉树，有t片树叶v1，v2，vt，分别带权W!，W2，Wt，则称T为赋权二叉树或带权二叉树。在赋权二叉树T中，称为树T的权。记为W(T)。在所有有t片树叶的二叉树中，如果t片树叶分别带权W!，W2，Wt，权W(T)最小的二叉树，称为最优二叉树。图9.48中的三棵树T1，T2和T3都是带权2，2，3，3，5的二叉树，它们的权分别是：W(T1)=2222335332=38 W(T2)=3454332221=47 W(T3)=3333522222=36 以上三棵树都是带权2,2,3,3,5的赋权二叉树，但不是最优树。,下面介绍一种求最优树方法，叫Huffman算法。它的基本思想是：给定t片树叶的权

46、为W1,W2,Wt且W1W2Wt。连接权为W1，W2的两片树叶，得一分枝点，其权为W1W2。在W1W2，W3，Wt中选出两个最小的权，连接它们对应的结点(不一定是树叶)，得新分枝点及所带的权。重复，直到形成t1个分枝点，t片树叶为止。,【例9.11】求带权2，2，3，3，5的最优二叉树T。解：图9.49给出了生成最优二叉树的过程。权2，2，3，3，5中最小的两个为2和2，2和2代表两片树叶，得一分枝点，其权为22=4，如图9.49(a)所示。在3，3，4，5中选出两个最小的权3和3,连接它们对应的结点，得新分枝点，该结点所带权为6，如图9.49(b)所示。在4，5，6中选出两个最小的权4和5,

47、连接它们对应的结点，得新分枝点，该结点所带权为9，如图9.49(c)所示。最后，连接6和9对应的结点得新分枝点，该分枝点所带权为15，如图9.49(d)所示。(d)是最优树。最优树的权为：W(T)=2323523232=34,二叉树的另一个应用是前缀码问题，下面介绍前缀码的基本概念和简单应用。,如果0、1序列a是另一个0、1序列b左起的一个连续部分，则称a是b的前缀。例如00是0001的前缀，000也是0001的前缀。而01不是0001的前缀。,定义9.6.15 给定一个0、1序列的集合。若没有一个序列是另一个序列的前缀，则称该集合为前缀码。例如1,00,011,0101,01001,0100

48、0是前缀码。而 1,00,0101,0100,01001,01000不是前缀码，因为0100是01001的前缀，也是01000的前缀。定理9.6.7 任意一个二叉树，可以产生惟一的前缀码。证明：在二叉树中，每一个分枝点引出的左侧边标记0，右侧边标记1。由根结点到树叶的路经上各边的标记组成的0、1序列作为该片树叶的标记。显然，没有一片树叶的标记是另一片树叶的标记的前缀。所有树叶的标记构成了一个前缀码。,【例9.12】求图9.50(a)所示的二叉树产生的前缀码。解：在图9.50(a)中，每一个分枝点引出的左侧边标记0，右侧边标记1。由根结点到树叶的路经上各边的标记组成的0、1序列作为对应树叶的标记

49、，如图9.50(b)所示。产生的前缀码为：01,11,000,0010,0011,定理9.6.8 任意一个前缀码，都对应一个二叉树。【例9.13】设1,01,000是一前缀码，画出对应一个二叉树。解：,9.7二部图及匹配 9.7.1二部图 定义9.7.1 G=V,E是无向图，V1V，V2V，满足：V1V2=V，V1V2=。G中每一条边的两端点，一个属于V1，另一个属于V2。则称G为二部图或偶图，常记为G=V1,V2,E，V1和V2称为G的互补的结点子集。二部图的每一条边的两个端点位于两个互补的结点子集，所以没有自回路。二部图是无自回路图。,定义9.7.2 设G=V1,V2,E是二部图，|V1|

50、=r,|V2|=s，若V1的每个结点和V2的所有结点邻接,则称G为完全二部图或完全偶图，常记为Kr,s。在图9.55中，(a)，(b)，(c)都是二部图，其中(b)，(c)是完全二部图K1,3和K3,3。,定理9.7.1 设G=V,E是无向图，G为二部图的充分必要条件是G的所有回路的长均为偶数。,9.7.2匹配 定义9.7.3 设G=V1,V2,E是二部图，M是G中一些边组成的集合，如果M中任意两条边都没有公共端点，则称M为G的一个匹配或对集。设v是G的结点，如果v是M中某条边的端点，则称v为M的饱和点。否则，称v为M的非饱和点。在图9.57中，边集M=(a1,b2),(a2,b3),(a4,