图的连通和矩阵表示及计算.ppt
《图的连通和矩阵表示及计算.ppt》由会员分享,可在线阅读,更多相关《图的连通和矩阵表示及计算.ppt(23页珍藏版)》请在三一文库上搜索。
1、图的连通性和矩阵表示及计算,3.2 图的连通性 3.2.1 连通性 如未说明,则本节的图G均是指无向图. 定义3.2.1 图G=中,设有结点vj与vk,若从vj到vk存在任何一条路径,则称结点vk从结点vj可达,也称结点vj与vk是连通的. 约定,对任意结点v,v与v是连通的. 定义3.2.2 若G是平凡图或G中任意两个结点都是连通的,则称G是连通图,否则,称G为非连通图或分离图. 定义3.2.3 设G=是图,连通关系的商集为V1,V2,.,Vm,则 其导出的子图G(Vi)(i=1,2,.,m)称为图G的连通分支,将图G的连通分支数记作W(G). 显然,如果图G只有一个连通分支,则G是连通图.
2、 见例1,定义3.2.4 设u与v是图G的两个结点,若u与v连通,则称u与v之间长度最短的路为u与v之间的短程线.短程线的长度可作为结点u与v间的距离,记作d(u,v).其满足下列性质: d(u,v)0,u=v时,d(u,v)=0 (非负性) d(u,v)=d(v,u) (对称性) d(u,v)+d(v,w)d(u,w) (三角不等式) 若u与v不连通,则通常记作d(u,v)=. 见例2 无向图的连通性不能直接推广到有向图.在有向图G中,可达性是结点集上的二元关系,其为自反的和传递的,但不是对称的,因若从u到v有一条路时,不一定必有v到u的一条路,故有向图的可达性不是等价关系.,若u,v可达,
3、其间可能不止一条路,在所有这些路中,最短路的长度称为结点u与v间的距离,记作d.其满足下列性质: (1) d0; (2) d=0; (3) d+dd; (4) 若u不可达v,则通常记作d=; (5) 若u可达v,且v可达u时,d不一定等于d. 见例3 定义3.2.5 在简单有向图中,若在任何结点偶对中,至少从一个结点到另一个结点是可达的,则称图G是单向(侧)连通的. 若在任何结点偶对中,两结点对互相可达,则称图G是强连通的; 若图G的底图,即在图G中略去边的方向,得到的无向图是连通的,则称图G是弱连通的. 显然,强连通的一定是单向连通的和弱连通的,单向连通的一定是弱连通的,但其逆均不真. 见例
4、3,定理3.2.1 一个有向图是强连通的,当且仅当G有一个回路,且其至少包含每个结点一次 证明见书. 定义3.2.6 在简单有向图G=中,G是G的子图,如果G是强连通的(单向连通的、弱连通的),且没有包含G的更大的子图G是强连通的(单向连通的、弱连通的),则称G是极大强连通(单向连通、弱连通)子图,又叫强分图(单向分图、弱分图). 定理3.2.2 在有向图G=中,G的每一结点都在也只在一个强(弱)分图中.(在无向图中,类似的定理也成立) 证明见书,结点在同一单向分图中是相容关系(具有自反的和对称的二元关系).相容关系把结点分成最大相容类,最大相容集合是集合V的一个覆盖.每个最大相容类的结点导出
5、一极大单向连通子图,因此有以下定理: 定理3.2.3 在有向图G=中,G的每一结点都处在一个或一个以上的单向分图中.,3.2.2 连通度 定义3.2.7 设无向图G=为连通图,若有点集V1 V,使图G删除了V1的所有结点后,所得的子图是不连通图,而删除了V1的任何真子集后,所得的子图是连通图,则称V1是G的一个点割集.若某个结点构成一个点割集,则称该结点为割点. 见例5 定义3.2.8 若G为无向连通图且不含Kn为生成子图,则称k(G)=minV1,其中V1是G的一个点割集为G的点连通度(简称连通度). 规定:完全图Kn的点连通度为n,n1. 非连通图的点连通度为0. 若k(G)k,则称G为k
6、-连通图. 显然,点连通度k(G)是产生一个不连通图所需要删除的点的最少数目. 见例6,定义3.2.9 设无向图G=为连通图,若有边集E1 E,使图G删除了E1的所有边后,所得的子图是不连通图,而删除了E1的任何真子集后,所得的子图是连通图,则称E 是G的一个边割集.若某个边构成一个边割集,则称该边为割边(或桥). 见例7 定义3.2.10 若G为无向连通图,则称(G)=min|E1|,其中E1是G的一个边割集为G的边连通度. 规定:非连通图的边连通度为0. 若(G)k,则称G为k边-连通图. 显然,边连通度(G)是产生一个不连通图所需要删除的边的最少数目.,定理3.2.4 对于任意图G,有
7、k(G)(G)(G) 其中,k(G),(G),(G)分别为G的点连通度、边连通度和最小度。 证明见书 定理3.2.5 一个连通无向图G中的结点v是割点的充分必要条件是存在两个结点u和w,使得结点u与w的每一条路都通过v. 证明见书.,3.3 图的矩阵表示与运算 3.3.1 设G=是一个简单图,其中V=v1,v2,.,vn,则n阶方阵A(G)=(aij)称为G的邻接矩阵.其中: ,vi与vj相邻 ,vi与vj不相邻或i=j 见例1 可以容易看出,当给定的简单图是无向图时,邻接矩阵为对称的.当给定的图是有向图时,邻接矩阵不一定对称. 显然,图G的邻接矩阵与结点标定的次序有关. 见例2 有关邻接矩阵
8、的一些性质与特征: (1) 图G的邻接矩阵是不唯一的,而是与V中的元素标定的次序有关.根据对图G的结点集V中各元素标定不同的次序,就可以得到图G的不同邻接矩阵,但这些邻接矩阵经过适当地交换行和列的次序,就可以从一个邻接矩阵变换到另一个邻接矩阵.根据这些不同的邻接矩阵所作的图都是同构的.,(2) 当有向线图代表关系时,邻接矩阵就可看做是一种关系矩阵. 有向线图代表关系是自反的,矩阵的对角线元素全为1; 有向线图代表关系是反自反的,矩阵的对角线元素全为0; 有向线图代表关系是对称的,矩阵是对称的; 有向线图代表关系是反对称的,矩阵中以主对角线对称的元素不可能同时为1. (3) 零图的邻接矩阵的元素
9、全为0,称该矩阵为零矩阵. (4) 当图的每一结点都有自回路而再无其他边时,图的邻接矩阵是单位矩阵. 从图G的邻接矩阵可以得到图的一些重要性质: (1) 有向图G的邻接矩阵中,第i行的元素是由结点vi出发的边所确定的,若矩阵中第i行第j列的元素为1,则表示在图G中结点vi和vj之间有一条边相连,其中vi为起点,vj为终点. (2) 有向图G的邻接矩阵中,第i行中值为1的元素的数目等于从vi发出的边数,即为结点vi的出度;第j列中值为1的元素的数目等于进入结点vj的边数,即为结点vj的入度.,(3) 结点间的通路数目在图形中很容易看出来,通过邻接矩阵的计算也可以获得,下面将说明利用矩阵乘法计算从
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 连通 矩阵 表示 计算
链接地址:https://www.31doc.com/p-3196576.html