资源描述：
《图的连通性和矩阵表示及计算》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
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的连通分支
2、,将图G的连通分支数记作W(G).显然,如果图G只有一个连通分支,则G是连通图.见例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中,可达性是结点集上的二
3、元关系,其为自反的和传递的,但不是对称的,因若从u到v有一条路时,不一定必有v到u的一条路,故有向图的可达性不是等价关系.若u,v可达,其间可能不止一条路,在所有这些路中,最短路的长度称为结点u与v间的距离,记作d.其满足下列性质:(1)d≥0;(2)d=0;(3)d+d≥d;(4)若u不可达v,则通常记作d=∞;(5)若u可达v,且v可达u时,d不一定等于d.见例3定义3.2.5在简单有向图中,若在任何结点偶对中,至少从一个结点
4、到另一个结点是可达的,则称图G是单向(侧)连通的.若在任何结点偶对中,两结点对互相可达,则称图G是强连通的;若图G的底图,即在图G中略去边的方向,得到的无向图是连通的,则称图G是弱连通的.显然,强连通的一定是单向连通的和弱连通的,单向连通的一定是弱连通的,但其逆均不真.见例3定理3.2.1一个有向图是强连通的,当且仅当G有一个回路,且其至少包含每个结点一次证明见书.定义3.2.6在简单有向图G=中,G'是G的子图,如果G'是强连通的(单向连通的、弱连通的),且没有包含G'的更大的子图G''是强连通的(单向连通
5、的、弱连通的),则称G'是极大强连通(单向连通、弱连通)子图,又叫强分图(单向分图、弱分图).定理3.2.2在有向图G=中,G的每一结点都在也只在一个强(弱)分图中.(在无向图中,类似的定理也成立)证明见书结点在同一单向分图中是相容关系(具有自反的和对称的二元关系).相容关系把结点分成最大相容类,最大相容集合是集合V的一个覆盖.每个最大相容类的结点导出一极大单向连通子图,因此有以下定理:定理3.2.3在有向图G=中,G的每一结点都处在一个或一个以上的单向分图中.3.2.2连通度定义3.2.7设无向图
6、G=为连通图,若有点集V1V,使图G删除了V1的所有结点后,所得的子图是不连通图,而删除了V1的任何真子集后,所得的子图是连通图,则称V1是G的一个点割集.若某个结点构成一个点割集,则称该结点为割点.见例5定义3.2.8若G为无向连通图且不含Kn为生成子图,则称k(G)=min｛V1｜,其中V1是G的一个点割集｝为G的点连通度(简称连通度).规定:完全图Kn的点连通度为n,n≥1.非连通图的点连通度为0.若k(G)≥k,则称G为k-连通图.显然,点连通度k(G)是产生一个不连通图所需要删除的点的最少数目.见例
7、6定义3.2.9设无向图G=为连通图,若有边集E1E,使图G删除了E1的所有边后,所得的子图是不连通图,而删除了E1的任何真子集后,所得的子图是连通图,则称E是G的一个边割集.若某个边构成一个边割集,则称该边为割边(或桥).见例7定义3.2.10若G为无向连通图,则称λ(G)=min｛
8、E1
9、｜,其中E1是G的一个边割集｝为G的边连通度.规定:非连通图的边连通度为0.若λ(G)≥k,则称G为k边-连通图.显然,边连通度λ(G)是产生一个不连通图所需要删除的边的最少数目.定理3.2.4对于任意图G,有k(G)≤
10、λ(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阶
