离散数学-图论1216版.ppt
《离散数学-图论1216版.ppt》由会员分享,可在线阅读,更多相关《离散数学-图论1216版.ppt(82页珍藏版)》请在三一办公上搜索。
1、第8章 图论,8.1 图的基本概念 8.2 路径和回路8.图的矩阵表示8.二部图8.5 平面图8.6 树8.7 有向树8.8 运输网络,问题是要从这四块陆地中任何一块开始,通过每一座桥正好一次,再回到起点。欧拉在1736年解决了这个问题。,判定法则:如果通奇数座桥的地方不止两个,那么满足要求的路线便不存在了。如果只有两个地方通奇数座桥,则可从其中任何一地出发找到所要求的路线。若没有一个地 方通奇数座桥,则从任何一地出发,所求的路线都能实现,定义8.11 一个图G是一个三重组V(G),E(G),G,其中V(G)是一个非空的结点(或叫顶点)集合,E(G)是边的集合,G是从边集E到结点偶对集合上的函
2、数。一个图可以用一个图形表示。例1设G=V(G),E(G),G,其中V(G)=a,b,c,d,E(G)=e1,e2,e3,e4,e5,e6,e7,G(e1)=(a,b),G(e2)=(a,c),G(e3)=(b,d),G(e4)=(b,c),G(e5)=(d,c),G(e6)=(a,d),G(e7)=(b,b)则图G可用图8.11表示。,8.1 图的基本概念,8.1.1 图,图 8.1-1,定义中的结点偶对可以是有序的,也可以是无序的。若边e所对应的偶对a,b是有序的,则称e是有向边。有向边简称弧,a叫弧e的始点,b叫弧e的终点,统称为e的端点。称e是关联于结点a和b的,结点a和结点b是邻接的
3、。若边e所对应的偶对(a,b)是无序的,则称e是无向边。无向边简称棱,除无始点和终点的术语外,其它术语与有向边相同。每一条边都是有向边的图称为有向图,第三章中的关系图都是有向图的例子。每一条边都是无向边的图称为无向图;如果在图中一些边是有向边,而另一些边是无向边,则称这个图是混合图。我们仅讨论有向图和无向图,且V(G)和E(G)限于有限集合。,约定用a,b表示有向边,(a,b)表示无向边,既表示有向边又表示无向边时用a,b。有向图和无向图也可互相转化。例如,把无向图中每一条边都看作两条方向不同的有向边,这时无向图就成为有向图。又如,把有向图中每条有向边都看作无向边,就得到无向图。这个无向图习惯
4、上叫做该有向图的底图。在图中,不与任何结点邻接的结点称为弧立结点;全由孤立结点构成的图称为零图。关联于同一结点的一条边称为自回路;自回路的方向不定。自回路的有无不使有关图论的各个定理发生重大变化,所以有许多场合都略去自回路。,在有向图中,两结点间(包括结点自身间)若同始点和同终点的边多于一条,则这几条边称为平行边。在无向图中,两结点间(包括结点自身间)若多于一条边,则称这几条边为平行边。两结点a、b间互相平行的边的条数称为边a,b的重数。仅有一条时重数为1,无边时重数为0。定义8.12含有平行边的图称为多重图。非多重图称为线图。无自回路的线图称为简单图。在图8.13中,(a)、(b)是多重图,
5、(c)是线图,(d)是简单图,关系图都是线图。,图 8.13,定义 8.13 赋权图G是一个三重组V,E,g或四重组V,E,f,g,其中V是结点集合,E是边的集合,f是定义在V上的函数,g是定义在E上的函数。右图给出一个赋权图。V=v1,v2,v3;E=e1,e2=(v1,v2),(v2,v3);f(v1)=5,f(v2)=8,f(v3)=11;g(e1)=4.6,g(e2)=7.5,8.1.2 结点的次数定义8.14在有向图中,对于任何结点v,以v为始点的边的条数称为结点v的引出次数(或出度),记为deg+(v);以v为终点的边的条数称为结点v的引入次数(或入度),记为deg-(v);结点v
6、的引出次数和引入次数之和称为结点v的次数(或度数),记作deg(v)。在无向图中,结点v的次数是与结点v相关联的边的条数,也记为deg(v)。孤立结点的次数为零。,定理8.11 设G是一个(n,m)图,它的结点集合为V=v1,v2,vn,则,证 因为每一条边提供两个次数,而所有各结点次数之和为m条边所提供,所以上式成立。在有向图中,上式也可写成:,定理8.12在图中,次数为奇数的结点必为偶数个。证 设次数为偶数的结点有n1个,记为(i=1,2,n1)。次数为奇数的结点有n2个,记为(i=1,2,n2)。由上一定理得,因为次数为偶数的各结点次数之和为偶数。所以前一项次数为偶数;若n2为奇数,则第
7、二项为奇数,两项之和将为奇数,但这与上式矛盾。故n2必为偶数。证毕。,定义8.15各结点的次数均相同的图称为正则图,各结点的次数均为k时称为k正则图。下图所示的称为彼得森(Petersen)图,是3正则图。,图 8.15,8.1.3 图的同构 定义设G=V,E和G=V,E是两个图,若存在从V到V的双射函数,使对任意a、bV,a,bE当且仅当(a),(b)E,并且a,b和(a),(b)有相同的重数,则称G和G是同构的。上述定义说明,两个图的各结点之间,如果存在一一对应关系,而且这种对应关系保持了结点间的邻接关系(在有向图时还保持边的方向)和边的重数,则这两个图是同构的,两个同构的图除了顶点和边的
8、名称不同外实际上代表同样的组合结构。,例2(a)、(b)两图是同构的。因为可作映射:g(1)=v3,g(2)=v1,g(3)=v4,g(4)=v2。在这映射下,边1,3,1,2,2,4和3,4分别映射到v3,v4,v3,v1,v1,v2和v4,v2,而后面这些边又是(b)中仅有的边。,图 8.16,两图同构的必要条件:(1)结点数相等;(2)边数相等;(3)度数相同的结点数相等。但这不是充分条件。例如下图中(a)、(b)两图虽然满足以上3条件,但不同构。(a)中的x应与(b)中的y对应,因为次数都是3。但(a)中的x与两个次数为1的点u,v邻接,而(b)中的y仅与一个次数为1的点w邻接。,图
9、8.17,8.1.4 图的运算图的常见运算有并、交、差、环和等,现分别定义于下:定义8.17设图G1=V1,E1和图G2=V2,E2(1)G1与G2的并,定义为图G3V3,E3,其中V3=V1V2,E3=E1E2,记为G3=G1G2。(2)G1与G2的交,定义为图G3V3,E3,其中V3=V1V2,E3=E1E2,记为G3=G1G2。,(3)G1与G2的差,定义为图G3V3,E3,记为G3=G1-G2。其中E3=E1-E2,V3=(V1-V2)E3中边所关联的顶点。(4)G1与G2的环和,定义为图G3V3,E3,G3=(G1G2)-(G1G2),记为G3=G1G2。,除以上4种运算外,还有以下
10、两种操作:(1)删去图G的一条边e;(2)删去图G的一个结点v。它的实际意义是删去结点v和与v关联的所有边。,图 8.19,8.1.5 子图与补图定义8.18设G=V,E 和G=V,E是两个图。(1)如果V V和E E,则称G是G的子图。如果V V和E E,则称G G的真子图。(注意:“G是图”已隐含着“E中的边仅关联V中的结点”的意义。)(2)如果V=V和E E,则称G为G的生成子图。(3)若子图G中没有孤立结点,G由E唯一确定,则称G为由边集E导出的子图。,(4)若在子图G中,对V中的任意二结点u、v,当u,vE时有u,vE,则G由V唯一确定,此时称G为由结点集V导出的子图。,图 8.11
11、0,定义8.19在n个结点的有向图G=V,E中,如果E=VV,则称G为有向完全图;在n个结点的无向图G=V,E中,如果任何两个不同结点间都恰有一条边,则称G为无向完全图,记为Kn。图8.111是4个结点的有向完全图和无向完全图的图示。,图8.1-11,定义8.110 设线图G=V,E有n个顶点,线图H=V,E也有同样的顶点,而E是由n个顶点的完全图的边删去E 所得,则图H称为图G的补图,记为,显然,。,8.2 路径和回路,8.2.1 路径和回路定义8.21在有向图中,从顶点v0到顶点vn的一条路径是图的一个点边交替序列(v0e1v1e2v2envn),其中vi-1和vi分别是边ei的始点和终点
12、,i=1,2,n。在序列中,如果同一条边不出现两次,则称此路径是简单路径,如果同一顶点不出现两次,则称此路径是基本路径(或叫链)。,基本路径也一定是简单路径。,如果路径的始点v0和终点vn相重合,即v0=vn,则此路径称为回路,没有相同边的回路称为简单回路,通过各顶点不超过一次的回路称为基本回路。(a)P1=(v1e1v2e7v5)是一条基本路径。(b)P2=(v2e2v3e3v3e4v1e1v2)是一简单回路但非基本回路。,图8.2-1,在无向图上,以上各术语的定义完全类似,故不重复。路径和回路可仅用边的序列表示,在非多重图时也可用顶点序列表示。,定义8.22 路径P中所含边的条数称为路径P
13、的长度。长度为0的路径定义为单独一个顶点。(但注意习惯上不定义长度为0的回路。)定理8.21在一个具有n个结点的简单图G=V,E中,如果从v1到v2有一条路径,则从v1到v2有一条长度不大于n-1的基本路径。,简证 假定从v1到v2存在一条路径,(v1,vi,v2)是所经的结点,如果其中有相同的结点vk,例(v1,vi,vk,vk,v2),则删去从vk到vk的这些边,它仍是从v1到v2的路径,如此反复地进行直至(v1,vi,v2)中没有重复结点为止。此时,所得的就是基本路径。基本路径的长度比所经结点数少1,图中共n个结点,故基本路径长度不超过n-1。,定理8.22在一个具有n个结点的简单图G=
14、V,E中,如果经v1有一条简单回路,则经v1有一条长度不超过n的基本回路。定义8.23在图G=V,E中,从结点vi到vj最短路径的长度叫从vi到vj的距离,记为d(vi,vj)。若从vi到vj不存在路径,则d(vi,vj)=。注意,在有向图中,d(vi,vj)不一定等于d(vj,vi),但一般地满足以下性质:(1)d(vi,vj)0;(2)d(vi,vi)=0;(3)d(vi,vj)+d(vj,vk)d(vi,vk)。,8.2.2 连通图定义8.24设G=V,E是图,且vi、vjV。如果从vi到vj存在一条路径,则称vj从vi可达。vi自身认为从vi可达。定义8.25在无向图G中,如果任两结点
15、可达,则称图G是连通的;如果G的子图G是连通的,没有包含G的更大的子图G是连通的,则称G是G的连通分图(简称分图)。,图8.22,一个无向图或者是一个连通图,如图8.22(a)所示,或者是由若干个连通分图组成,如图8.22(b)所示。,定理8.23设G是任一(n,m)无向简单图,是其分图个数,则,定义8.26在有向图中,如果在任两结点偶对中,至少从一个结点到另一个结点是可达的,则称图G是单向连通的;如果在任两结点偶对中,两结点都互相可达,则称图G是强连通的;如果它的底图是连通的,则称图G是弱连通的。,强连通的也一定是单向连通和弱连通的,单向连通的一定是弱连通的,但其逆均不真。在下图中,(a)是
16、强连通的,(b)是单向连通的,(c)是弱连通的。,定义8.27在有向图G=V,E中,G是G的子图,若G是强连通的(单向连通的,弱连通的),没有包含G的更大子图G是强连通的(单向连通的,弱连通的),则称G是G的强分图(单向分图,弱分图)。在下图中,强分图集合是: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,8.2.3 赋权图中的最短路径设G=V,E,W是个赋权图,W是从E到正实数集合的函数,
17、边i,j的权记为W(i,j),称为边的长度。若i和j之间没有边,那么W(i,j)=。路径P的长度定义为路径中边的长度之和,记为W(P)。图G中从结点u到结点v的距离记为d(u,v),定义为 minW(P)|P为G中从u到v的路径 当从u到v不可达时,本小节主要讨论在一个赋权的简单连通无向图 G=V,E,W中,求一结点a(称为源点)到其它结点x的最短路径的长度,通常称它为单源问题。下面介绍1959年迪克斯特拉(E.W.Dijkstra)提出的单源问题的算法,其要点如下:(1)把V分成两个子集S和T。初始时,S=a,T=V-S。(2)对T中每一元素t计算D(t),根据D(t)值找出T中距a最短的一
18、结点x,写出a到x的最短路径的长度D(x)。(3)置S为Sx,置T为T-x,若T=,则停止,否则再重复2。,算法中步骤(1)和(3)是清楚的,现在对2给以说明。D(t)表示从a到t的不包含T中其它结点的最短通路的长度,但D(t)不一定是从a到t的距离,因为从a到t可能有包含T中另外结点的更短通路。首先我们证明“若x是T中具有最小D值的结点,则D(x)是从a到x的距离”,用反证法。若另有一条含有T中另外结点的更短通路,不妨设这个通路中第一个属于T-x的结点是t1,于是D(t1)D(x),但这与题设矛盾。可见以上断言成立。,其次说明计算D(t)的方法。初始时,D(t)=W(a,t),现在我们假设对
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 离散数学 图论 1216
![提示](https://www.31ppt.com/images/bang_tan.gif)
链接地址:https://www.31ppt.com/p-6326489.html