图的基本概念.ppt
- 文档编号:18720359
- 上传时间:2023-10-18
- 格式:PPT
- 页数:80
- 大小:1.32MB
图的基本概念.ppt
《图的基本概念.ppt》由会员分享,可在线阅读,更多相关《图的基本概念.ppt(80页珍藏版)》请在冰点文库上搜索。
第14章图的基本概念,离散数学,中国地质大学本科生课程,本章内容,14.1图14.2通路与回路14.3图的连通性14.4图的矩阵表示14.5图的运算基本要求作业,14.1图的基本概念,图的定义图的一些概念和规定简单图和多重图顶点的度数与握手定理图的同构完全图与正则图子图与补图,无序积与多重集合,设A,B为任意的两个集合,称a,b|aAbB为A与B的无序积,记作A&B。
可将无序积中的无序对a,b记为(a,b),并且允许ab。
无论a,b是否相等,均有(a,b)(b,a),因而A&BB&A。
元素可以重复出现的集合称为多重集合或者多重集,某元素重复出现的次数称为该元素的重复度。
例如在多重集合a,a,b,b,b,c,d中,a,b,c,d的重复度分别为2,3,1,1。
定义14.1一个无向图是一个有序的二元组,记作G,其中
(1)V称为顶点集,其元素称为顶点或结点。
(2)E称为边集,它是无序积V&V的多重子集,其元素称为无向边,简称边。
定义14.2一个有向图是一个有序的二元组,记作D,其中
(1)V称为顶点集,其元素称为顶点或结点。
(2)E为边集,它是笛卡儿积VV的多重子集,其元素称为有向边,简称边。
无向图和有向图,说明,可以用图形表示图,即用小圆圈(或实心点)表示顶点,用顶点之间的连线表示无向边,用有方向的连线表示有向边。
例14.1,例14.1
(1)给定无向图G,其中Vv1,v2,v3,v4,v5,E=(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5).
(2)给定有向图D=,其中Va,b,c,d,E,。
画出G与D的图形。
图的一些概念和规定,G表示无向图,但有时用G泛指图(无向的或有向的)。
D只能表示有向图。
V(G),E(G)分别表示G的顶点集和边集。
若|V(G)|n,则称G为n阶图。
若|V(G)|与|E(G)|均为有限数,则称G为有限图。
若边集E(G),则称G为零图,此时,又若G为n阶图,则称G为n阶零图,记作Nn,特别地,称N1为平凡图。
在图的定义中规定顶点集V为非空集,但在图的运算中可能产生顶点集为空集的运算结果,为此规定顶点集为空集的图为空图,并将空图记为。
标定图与非标定图、基图,将图的集合定义转化成图形表示之后,常用ek表示无向边(vi,vj)(或有向边),并称顶点或边用字母标定的图为标定图,否则称为非标定图。
将有向图各有向边均改成无向边后的无向图称为原来图的基图。
易知标定图与非标定图是可以相互转化的,任何无向图G的各边均加上箭头就可以得到以G为基图的有向图。
关联与关联次数、环、孤立点,设G为无向图,ek(vi,vj)E,称vi,vj为ek的端点,ek与vi或ek与vj是彼此相关联的。
若vivj,则称ek与vi或ek与vj的关联次数为1。
若vivj,则称ek与vi的关联次数为2,并称ek为环。
任意的vlV,若vlvi且vlvj,则称ek与vl的关联次数为0。
设D为有向图,ekE,称vi,vj为ek的端点。
若vivj,则称ek为D中的环。
无论在无向图中还是在有向图中,无边关联的顶点均称为孤立点。
相邻与邻接,设无向图G,vi,vjV,ek,elE。
若etE,使得et(vi,vj),则称vi与vj是相邻的。
若ek与el至少有一个公共端点,则称ek与el是相邻的。
设有向图D,vi,vjV,ek,elE。
若etE,使得et,则称vi为et的始点,vj为et的终点,并称vi邻接到vj,vj邻接于vi。
若ek的终点为el的始点,则称ek与el相邻。
邻域,设无向图G,vV,称u|uV(u,v)Euv为v的邻域,记做NG(v)。
称NG(v)v为v的闭邻域,记做NG(v)。
称e|eEe与v相关联为v的关联集,记做IG(v)。
设有向图D,vV,称u|uVEuv为v的后继元集,记做+D(v)。
称u|uVEuv为v的先驱元集,记做-D(v)。
称+D(v)-D(v)为v的邻域,记做ND(v)。
称ND(v)v为v的闭邻域,记做ND(v)。
举例,NG(v1),+D(d),v2,v5,NG(v1),v1,v2,v5,IG(v1),e1,e2,e3,c,-D(d),a,c,ND(d),a,c,ND(d),a,c,d,简单图与多重图,定义14.3在无向图中,关联一对顶点的无向边如果多于1条,则称这些边为平行边,平行边的条数称为重数。
在有向图中,关联一对顶点的有向边如果多于1条,并且这些边的始点和终点相同(也就是它们的方向相同),则称这些边为平行边。
含平行边的图称为多重图。
既不含平行边也不含环的图称为简单图。
例如:
在图14.1中,(a)中e5与e6是平行边,(b)中e2与e3是平行边,但e6与e7不是平行边。
(a)和(b)两个图都不是简单图。
顶点的度数,定义14.4设G为一无向图,vV,称v作为边的端点次数之和为v的度数,简称为度,记做dG(v)。
在不发生混淆时,简记为d(v)。
设D为有向图,vV,称v作为边的始点次数之和为v的出度,记做dD-(v),简记作d-(v)。
称v作为边的终点次数之和为v的入度,记做d+D(v),简记作d+(v)。
称d-(v)+d+(v)为v的度数,记做d(v)。
图的度数的相关概念,在无向图G中,最大度(G)maxd(v)|vV(G)最小度(G)mind(v)|vV(G)在有向图D中,最大入度+(D)maxd+(v)|vV(D)最小入度+(D)mind+(v)|vV(D)最大出度-(D)maxd-(v)|vV(D)最小出度-(D)mind-(v)|vV(D)称度数为1的顶点为悬挂顶点,与它关联的边称为悬挂边。
度为偶数(奇数)的顶点称为偶度(奇度)顶点。
图的度数举例,d(v1)4(注意,环提供2度),4,1,v4是悬挂顶点,e7是悬挂边。
d-(a)4,d+(a)1(环e1提供出度1,提供入度1),d(a)4+15。
5,3,-4(在a点达到)-0(在b点达到)+3(在b点达到)+1(在a和c点达到),握手定理,定理14.1设G为任意无向图,Vv1,v2,vn,|E|m,则,说明任何无向图中,各顶点度数之和等于边数的两倍。
证明G中每条边(包括环)均有两个端点,所以在计算G中各顶点度数之和时,每条边均提供2度,当然,m条边,共提供2m度。
定理14.2设D为任意有向图,Vv1,v2,vn,|E|m,则,握手定理的推论,推论任何图(无向的或有向的)中,奇度顶点的个数是偶数。
证明设G为任意一图,令V1v|vVd(v)为奇数V2v|vVd(v)为偶数则V1V2V,V1V2,由握手定理可知,由于2m和,,所以,为偶数,,但因V1中顶点度数为奇数,,所以|V1|必为偶数。
问题研究,问题:
在一个部门的25个人中间,由于意见不同,是否可能每个人恰好与其他5个人意见一致?
解答:
不可能。
考虑一个图,其中顶点代表人,如果两个人意见相同,可用边连接,所以每个顶点都是奇数度。
存在奇数个度数为奇数的图,这是不可能的。
说明:
(1)很多离散问题可以用图模型求解。
(2)为了建立一个图模型,需要决定顶点和边分别代表什么。
(3)在一个图模型中,边经常代表两个顶点之间的关系。
度数列,设G为一个n阶无向图,Vv1,v2,vn,称d(v1),d(v2),d(vn)为G的度数列。
对于顶点标定的无向图,它的度数列是唯一的。
反之,对于给定的非负整数列dd1,d2,dn,若存在Vv1,v2,vn为顶点集的n阶无向图G,使得d(vi)di,则称d是可图化的。
特别地,若所得图是简单图,则称d是可简单图化的。
类似地,设D为一个n阶有向图,Vv1,v2,vn,称d(v1),d(v2),d(vn)为D的度数列,另外称d+(v1),d+(v2),d+(vn)与d-(v1),d-(v2),d-(vn)分别为D的出度列和入度列。
度数列举例,按顶点的标定顺序,度数列为4,4,2,1,3。
按字母顺序,度数列,出度列,入度列分别为5,3,3,34,0,2,11,3,1,2,可图化的充要条件,定理14.3设非负整数列d(d1,d2,dn),则d是可图化的当且仅当,证明必要性。
由握手定理显然得证。
充分性。
由已知条件可知,d中有偶数个奇数度点。
奇数度点两两之间连一边,剩余度用环来实现。
定理14.3的证明,由握手定理可知必然性显然。
下面证明充分性。
由已知条件可知,d中有2k(0kn/2)个奇数,不妨设它们为d1,d2,dk,dk+1,dk+2,d2k。
可用多种方法做出n阶无向图G,Vv1,v2,vn。
比如边集如下产生:
在顶点vr与vr+k之间连边,r1,2,k。
若di为偶数,令didi,若di为奇数,令didi-1,得d(d1,d2,dn),则di均为偶数。
再在vi处做出di/2条环,i1,n,将所得各边集合在一起组成E,则G的度数列为d。
其实,di为偶数时,d(vi)2di/22di/2di,当di为奇数时,d(vi)1+2di/21+di1+di-1di,这就证明了d是可图化的。
可图化举例,由定理14.3立即可知,(3,3,2,1),(3,2,2,1,1)等是不可图化的,(3,3,2,2),(3,2,2,2,1)等是可图化的。
定理14.4,定理14.4设G为任意n阶无向简单图,则(G)n-1。
证明因为G既无平行边也无环,所以G中任何顶点v至多与其余的n-1个顶点均相邻,于是d(v)n-1,由于v的任意性,所以(G)n-1。
例14.2判断下列各非负整数列哪些是可图化的?
哪些是可简单图化的?
(1)(5,5,4,4,2,1)不可图化。
(2)(5,4,3,2,2)可图化,不可简单图化。
若它可简单图化,设所得图为G,则(G)max5,4,3,2,25,这与定理14.4矛盾。
例14.2,(3)(3,3,3,1)可图化,不可简单图化。
假设该序列可以简单图化,设G以该序列为度数列。
不妨设Vv1,v2,v3,v4且d(v1)d(v2)d(v3)3,d(v4)1,由于d(v4)1,因而v4只能与v1,v2,v3之一相邻,于是v1,v2,v3不可能都是3度顶点,这是矛盾的,因而(3)中序列也不可简单图化。
(4)(d1,d2,dn),d1d2dn1且为偶数。
可图化,不可简单图化。
例14.2,(5)(4,4,3,3,2,2)可简单图化。
下图中两个6阶无向简单图都以(5)中序列为度数列。
图的同构,定义14.5设G1,G2为两个无向图,若存在双射函数f:
V1V2,对于vi,vjV1,(vi,vj)E1当且仅当(f(vi),f(vj)E2,并且(vi,vj)与(f(vi),f(vj)的重数相同,则称G1与G2是同构的,记做G1G2。
说明
(1)类似地,可以定义两个有向图的同构。
(2)图的同构关系看成全体图集合上的二元关系。
(3)图的同构关系是等价关系。
(4)在图同构的意义下,图的数学定义与图形表示是一一对应的。
图的同构举例,彼得森(Petersen)图,完全图,定义14.6设G为n阶无向简单图,若G中每个顶点均与其余的n-1个顶点相邻,则称G为n阶无向完全图,简称n阶完全图,记做Kn(n1)。
设D为n阶有向简单图,若D中每个顶点都邻接到其余的n-1个顶点,又邻接于其余的n-1个顶点,则称D是n阶有向完全图。
设D为n阶有向简单图,若D的基图为n阶无向完全图Kn,则称D是n阶竞赛图。
完全图举例,n阶无向完全图的边数为:
n(n-1)/2n阶有向完全图的边数为:
n(n-1)n阶竞赛图的边数为:
n(n-1)/2,K5,3阶有向完全图,4阶竞赛图,正则图,定义14.7设G为n阶无向简单图,若vV(G),均有d(v)k,则称G为k-正则图。
举例n阶零图是0-正则图n阶无向完全图是(n-1)-正则图彼得森图是3-正则图说明n阶k-正则图中,边数mkn/2。
当k为奇数时,n必为偶数。
子图,定义14.8设G,G为两个图(同为无向图或同为有向图),若VV且EE,则称G是G的子图,G为G的母图,记作GG。
若VV或EE,则称G为G的真子图。
若VV,则称G为G的生成子图。
设G为一图,V1V且V1,称以V1为顶点集,以G中两个端点都在V1中的边组成边集E1的图为G的V1导出的子图,记作GV1。
设E1E且E1,称以E1为边集,以E1中边关联的顶点为顶点集V1的图为G的E1导出的子图,记作GE1。
导出子图举例,在上图中,设G为
(1)中图所表示,取V1a,b,c,则V1的导出子图GV1为
(2)中图所示。
取E1e1,e3,则E1的导出子图GE1为(3)中图所示。
例14.3,
(1)画出4阶3条边的所有非同构的无向简单图。
由握手定理可知,所画的无向简单图各顶点度数之和为236,最大度小于或等于3。
于是所求无向简单图的度数列应满足的条件是,将6分成4个非负整数,每个整数均大于或等于0且小于或等于3,并且奇数的个数为偶数。
将这样的整数列排出来只有下面三种情况:
(1)2,2,1,1
(2)3,1,1,1(3)2,2,2,0,将每种度数列所有非同构的图都画出来即得所要求的全部非同构的图。
对于给定的正整数n和m(mn(n-1)/2),构造出所有非同构的n阶m条边的所有非同构的无向(有向)简单图,这是目前还没有解决的难题。
例14.3,
(2)画出3阶2条边的所有非同构的有向简单图。
由握手定理可知,所画有向简单图各顶点度数之和为4,最大出度和最大入度均小于或等于2。
度数列及入度出度列为,1,2,1,入度列为0,1,1或0,2,0或1,0,1,出度列为1,1,0或1,0,1或0,2,0,2,2,0,入度列为1,1,0,出度列为1,1,0,定义14.9,定义14.9设G为n阶无向简单图,以V为顶点集,以所有使G成为完全图Kn的添加边组成的集合为边集的图,称为G的补图,记作G。
若图GG,则称为G是自补图。
(1)为自补图
(2)和(3)互为补图,定义14.10,定义14.10设G为无向图。
(1)设eE,用G-e表示从G中去掉边e,称为删除e。
设EE,用G-E表示从G中删除E中所有的边,称为删除E。
(2)设vV,用G-v表示从G中去掉v及所关联的一切边,称为删除顶点v。
设VV,用G-V表示从G中删除V中所有顶点,称为删除V。
(3)设边e(u,v)E,用Ge表示从G中删除e后,将e的两个端点u,v用一个新的顶点w(或用u或v充当w)代替,使w关联除e外u,v关联的所有边,称为边e的收缩。
(4)设u,vV(u,v可能相邻,也可能不相邻),用G(u,v)(或G+(u,v)表示在u,v之间加一条边(u,v),称为加新边。
说明在收缩边和加新边过程中可能产生环和平行边。
举例,G,Ge5,Ge1,e4,Gv5,Gv4,v5,Ge5,14.2通路与回路,定义14.11设G为无向标定图,G中顶点与边的交替序列vi0ej1vi1ej2vi2ejivil称为vi0到vil的通路,其中,vir-1,vir为ejr的端点,r1,2,l,vi0,vil分别称为的始点与终点,中边的条数称为它的长度。
若vi0vil,则称通路为回路。
若的所有边各异,则称为简单通路,又若vi0vil,则称为简单回路。
若的所有顶点(除vi0与vij可能相同外)各异,所有边也各异,则称为初级通路或路径,又若vi0vil,则称为初级回路或圈。
将长度为奇数的圈称为奇圈,长度为偶数的圈称为偶圈。
关于通路与回路的说明,在初级通路与初级回路的定义中,仍将初级回路看成初级通路(路径)的特殊情况,只是在应用中初级通路(路径)都是始点与终点不相同的,长为1的圈只能由环生成,长为2的圈只能由平行边生成,因而在简单无向图中,圈的长度至少为3。
若中有边重复出现,则称为复杂通路,又若vi0vil,则称为复杂回路。
在有向图中,通路、回路及分类的定义与无向图中非常相似,只是要注意有向边方向的一致性。
在以上的定义中,将回路定义成通路的特殊情况,即回路也是通路,又初级通路(回路)是简单通路(回路),但反之不真。
通路和回路的简单表示法,只用边的序列表示通路(回路)。
定义14.11中的可以表示成ej1,ej2,ejl。
在简单图中也可以只用顶点序列表示通路(回路)。
定义中的也可以表示成vi0,vi2,vil。
为了写出非标定图中的通路(回路),可以先将非标定图标成标定图,再写出通路与回路。
在非简单标定图中,当只用顶点序列表示不出某些通路(回路)时,可在顶点序列中加入一些边(这些边是平行边或环),可称这种表示法为混合表示法。
定理14.5,定理14.5在n阶图G中,若从顶点vi到vj(vivj)存在通路,则从vi到vj存在长度小于或等于n-1的通路。
证明设v0e1v1e2elvl(v0vi,vlvj)为G中一条长度为l的通路,若ln-1,则满足要求,否则必有l+1n,即上的顶点数大于G中的顶点数,于是必存在k,s,0ksl,使得vsvk,即在上存在vs到自身的回路Csk,在上删除Csk上的一切边及除vs外的一切顶点,得v0e1v1e2vkes+1elvl,仍为vi到vj的通路,且长度至少比减少1。
若还不满足要求,则重复上述过程,由于G是有限图,经过有限步后,必得到vi到vj长度小于或等于n-1的通路。
定理14.6,推论在n阶图G中,若从顶点vi到vj(vivj)存在通路,则vi到vj一定存在长度小于或等于n-1的初级通路(路径)。
定理14.6在一个n阶图G中,若存在vi到自身的回路,则一定存在vi到自身长度小于或等于n的回路。
推论在一个n阶图G中,若存在vi到自身的简单回路,则一定存在vi到自身长度小于或等于n的初级回路。
例14.4,例14.4无向完全图Kn(n3)中有几种非同构的圈?
解答长度相同的圈都是同构的,因而只有长度不同的圈才是非同构的,易知Kn(n3)中含长度为3,4,n的圈,所以Kn(n3)中有n-2种非同构的圈。
例14.5,例14.5无向完全图K3的顶点依次标定为a,b,c。
在定义意义下K3中有多少个不同的圈?
解答在同构意义下,K3中只有一个长度为3的圈。
但在定义意义下,不同起点(终点)的圈是不同的,顶点间排列顺序不同的圈也看成是不同的,因而K3中有6个不同的长为3的圈:
abca,acba,bacb,bcab,cabc,cbac如果只考虑起点(终点)的差异,而不考虑顺时针逆时针的差异,应有3种不同的圈,当然它们都是同构的,画出图来只有一个。
14.3图的连通性,无向图的连通性无向图中顶点之间的短程线及距离无向图的连通程度:
点割集、割点、边割集、割边、连通度有向图的连通性及判别方法扩大路径法与极大路径二部图及其判别方法,无向图的连通性,定义14.12设无向图G,u,vV,若u,v之间存在通路,则称u,v是连通的,记作uv。
vV,规定vv。
无向图中顶点之间的连通关系(u,v)|u,vV且u与v之间有通路是自反的、对称的、传递的,因而是V上的等价关系。
连通图与连通分支,若无向图G是平凡图或G中任何两个顶点都是连通的,则称G为连通图,否则称G是非连通图或分离图。
说明:
完全图Kn(n1)都是连通图零图Nn(n2)都是分离图。
定义14.13设无向图G,V关于顶点之间的连通关系的商集V/V1,V2,Vk,Vi为等价类,称导出子图GVi(i1,2,k)为G的连通分支,连通分支数k常记为p(G)。
说明若G为连通图,则p(G)1。
若G为非连通图,则p(G)2。
在所有的n阶无向图中,n阶零图是连通分支最多的,p(Nn)n。
无向图中顶点之间的短程线及距离,定义14.14设u,v为无向图G中任意两个顶点,若uv,称u,v之间长度最短的通路为u,v之间的短程线,短程线的长度称为u,v之间的距离,记作d(u,v)。
当u,v不连通时,规定d(u,v)。
距离有以下性质:
(1)d(u,v)0,uv时,等号成立。
(2)具有对称性,d(u,v)d(v,u)。
(3)满足三角不等式:
u,v,wV(G),则d(u,v)+d(v,w)d(u,w)说明:
在完全图Kn(n2)中,任何两个顶点之间的距离都是1。
在n阶零图Nn(n2)中,任何两个顶点之间的距离都为。
如何定义连通度,问题:
如何定量地比较无向图的连通性的强与弱?
点连通度:
为了破坏连通性,至少需要删除多少个顶点?
边连通度:
为了破坏连通性,至少需要删除多少条边?
“破坏连通性”是指“变得更加不连通”。
无向图的点割集,定义14.15设无向图G,若存在VV,且V,使得p(G-V)p(G),而对于任意的VV,均有p(G-V)p(G),则称V是G的点割集。
若V是单元集,即Vv,则称v为割点。
v2,v4,v3,v5都是点割集v3,v5都是割点v1与v6不在任何割集中。
无向图的边割集,定义14.16设无向图G,若存在EE,且E,使得p(G-E)p(G),而对于任意的EE,均有p(G-E)p(G),则称E是G的边割集,或简称为割集。
若E是单元集,即Ee,则称e为割边或桥。
e6,e5,e2,e3,e1,e2,e3,e4,e1,e4,e1,e3,e2,e4都是割集,e6,e5是桥。
点连通度,定义14.17设G为无向连通图且为非完全图,则称K(G)min|V|V为G的点割集为G的点连通度,简称连通度。
说明连通度是为了产生一个不连通图需要删去的点的最少数目。
规定完全图Kn(n1)的点连通度为n-1,规定非连通图的点连通度为0,若K(G)k,则称G是k-连通图,k为非负整数。
说明K(G)有时简记为K。
上例中图的点连通度为1,此图为1-连通图。
K5的点连通度K4,所以K5是1-连通图,2-连通图,3-连通图,4-连通图。
若G是k-连通图(k1)则在G中删除任何k-1个顶点后,所得图一定还是连通的。
边连通度,定义14.18设G是无向连通图,称(G)min|E|E是G的点割集为G的边连通度。
规定非连通图的边连通度为0。
若(G)r,则称G是r边-连通图。
说明(G)也可以简记为。
若G是r边-连通图,则在G中任意删除r-1条边后,所得图依然是连通的。
完全图Kn的边连通度为n-1,因而Kn是r边-连通图,0rn-1。
图14.8中图的边连通度1,它只能是1边-连通图。
例14.6,求所示各图的点连通度,边连通度,并指出它们各是几连通图及几边连通图。
最后将它们按点连通程度及边连通程度排序。
K4,K3,K2,K1,K=1=2,K2,K0,K0,例14.6的解答,设第i个图的点连通度为Ki,边连通度为i,I1,2,8。
容易看出,K114,K223,K332,K441,K5=15=2,K662,K770,K880。
(1)是k-连通图,k边-连通图,k1,2,3,4。
(2)是k-连通图,k边-连通图,k1,2,3。
(3)是k-连通图,k边-连通图,k1,2。
(4)是1-连通图,1边-连通图。
(5)是1-连通图,k边-连通图,k1,2。
(6)是k-连通图,k边-连通图,k1,2。
(7)是0-连通图,0边-连通图。
(8)是0-连通图,0边-连通图。
点连通程度为
(1)
(2)(3)(6)(4)(5)(7)(8)。
边连通程度为
(1)
(2)(3)(5)(6)(4)(7)(8)。
定理14.7,定理14.7对于任何无向图G,有K(G)(G)(G)例14.7
(1)给出一些无向简单图,使得K。
(2)给出一些无向简单图,使得K。
解答
(1)n阶无向完全图Kn和n阶零图Nn都满足要求。
(2)在两个Kn(n4)之间放置一个顶点v,使v与两个Kn中的每一个的任意两个不同的顶点相邻,所得简单图满足要求。
因为这样的图中有一个割点,所以点连通度为1,又因为无桥,而有两条边组成的边割集,所以边连通度为2,当n4时,3,当n5时,4。
有向图的连通性,定义14.19设D为一个有向图。
vi,vjV,若从vi到vj存在通路,则称vi可达vj,记作vivj,规定vi总是可达自身的,即vivi。
若vivj且vjvi,则称vi与vj是相互可达的,记作vivj。
规定vivi。
说明与都是V上的二元关系,并且不难看出是V上的等价关系。
定义14.20设D为有向图,vi,vjV,若vivj,称vi到vj长度最短的通路为vi到vj的短程线,短程
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 基本概念