程序源代码下载网站,百度账号怎么注册,免费logo图标生成,wordpress创建中英文概念#xff08;1-4#xff09;都是针对无向图的
1.连通图 图中从一个顶点到达另一顶点#xff0c;若存在至少一条路径#xff0c;则称这两个顶点是连通着的。例如图 1 中#xff0c;虽然 V1 和 V3 没有直接关联#xff0c;但从 V1 到 V3 存在两条路径#xff0c;分别是…概念1-4都是针对无向图的
1.连通图 图中从一个顶点到达另一顶点若存在至少一条路径则称这两个顶点是连通着的。例如图 1 中虽然 V1 和 V3 没有直接关联但从 V1 到 V3 存在两条路径分别是 V1-›V2-›V3 和 V1-›V4-›V3因此称 V1 和 V3 之间是连通的。
图 1 顶点之间的连通状态示意图 无向图中如果任意两个顶点之间都能够连通则称此无向图为连通图。
2.极大连通子图 子图设G V,E, G’ V’,E’为两个图同为无向图或同为有向图若V’ ∈ \in ∈V 且 E’ ∈ \in ∈E则称G’是G的子图G是G’的母图。 极大连通子图对于图的某一子图它包含了图中尽可能多的顶点以及尽可能多的边以至于它再加上一个点或者边之后它就不连通了此时这个图就是极大连通子图。 对于连通无向图只有一个连通分量也就是只有一个极大连通子图就是它本身。 非连通图有多个极大连通子图也就是有多个连通分量。
3.连通分量极大连通子图 无向图G的极大连通子图称为G的连通分量。 如图 2所示虽然图 2 a) 中的无向图不是连通图但可以将其分解为3个“ 最大子图”图2 b)它们都满足极大连通子图的性质因此都是连通分量也都是极大连通子图。
图 2 连通分量示意图 所以连通分量和极大连通子图是同一个概念连通分量主要是对非连通图来说的因为连通图是一个整体分量是对非整体来说的对于连通图其连通分量和极大连通子图都是连通图本身。 理解了极大连通子图的概念就不会误以为极大连通子图是最大的那一个子图其含义是大到再加边或者点之后就不能连通的子图。因此图2 b)中的3个子图都是极大连通子图。
4.极小连通子图只存在于连通图中对于非连通图的意义不大
生成树对一个具有 n 个点的连通图进行遍历对于遍历后的子图其包含原图中所有的点且保持图连通最后的结构一定是一个具有 n-1 条边的树通常称为生成树。所以生成树是对于连通图来说的 极小连通子图“极小”是指边最少的连通子图去掉任何一个边都会使其变的不连通。所以一个连通图的生成树是该连通图顶点集确定的极小连通子图。 其实极小连通子图的概念是用来辅助定义生成树的概念的。
概念5-8都是针对有向图的
5.强连通图 有向图中若任意两个顶点 V i V_i Vi和 V j V_j Vj满足从 V i V_i Vi到 V j V_j Vj以及从 V j V_j Vj到 V i V_i Vi都连通也就是都含有至少一条通路则称此有向图为强连通图。如图3所示就是一个强连通图。
图 3 强连通图 可以这样说连通图是在无向图的基础上对图中顶点之间的连通做了更高的要求而强连通图是在有向图的基础上对图中顶点的连通做了更高的要求。
6.极大强连通子图 此概念和无向图的“极大连通子图”的概念类似只是前者是对有向图而言后者是对无向图而言。
7.强连通分量 此概念和无向图的“连通分量”的概念类似只是前者是对有向图而言后者是对无向图而言。 如图4中的2个子图都是强连通分量也都是极大强连通子图。
图 4 强连通分量 8.极小强连通子图 有向图并无此概念。
声明 本资料是我本人整合网上的资料得来的主要是因为发现很多帖子讲不清楚这个几个概念很多发帖人自己并未真正理解这些概念之间的区别读者看了并不能学到正确的知识。所以我一边学习一边整理出了这篇文章本人所作也并非都是正确的如有错误还望指正。
