图的割集和割顶点
是否可以从一个顶点到另一个顶点遍历图取决于图的连接方式。连接性是图论中的一个基本概念。连接性定义图形是已连接还是已断开。
连接性
如果每对顶点之间都有一条路径,则称该图是连通的。从每个顶点到任何其他顶点,都应该有一些遍历的路径。这称为图的连通性。具有多个不连续的顶点和边的图形被称为不连续的。
切顶点
令“G”为连通图。如果“GV”(从“G”中删除“V”)导致图形断开,则顶点V∈G称为“G”的割顶点。从图形中删除切割的顶点会将其分成两个或多个图形。
注意-删除切出的顶点可能会使图形断开连接。
连通图“G”最多可以具有(n–2)个切割顶点。
示例
在下图中,顶点“e”和“c”是剪切顶点。
通过删除“e”或“c”,该图将变为断开连接的图。
如果没有'g',则顶点'c'和顶点'h'以及其他许多顶点之间就没有路径。因此,它是一个断开的图,其顶点为“e”。类似地,“c”也是上图的割点。
切边(桥)
令“G”为连通图。如果'Ge'导致图形断开,则边缘'e'∈G称为切边。
如果删除图形中的一条边导致生成两个或更多图形,则该边称为“剪切边”。
示例
在下图中,切割边为[(c,e)]
通过从图形中删除边缘(c,e),它变为断开连接的图形。
在上面的图形中,删除边(c,e)会将图形分为两部分,这只是一个断开的图形。因此,边缘(c,e)是图形的切割边缘。
注意-假设'G'是具有'n'个顶点的连通图,则
当且仅当边缘'e'不属于G中任何循环的一部分时,才确定切割边缘e∈G。
可能的最大切边数量为“n-1”。
每当存在切边时,也存在切点,因为切边的至少一个顶点是切点。
如果存在切割顶点,则切割边缘可能存在或可能不存在。
图的割集
令'G'=(V,E)为连通图。如果从G中删除E'的所有边缘使G断开连接,则E的子集E'被称为G的割集。
如果从图形中删除一定数量的边使其断开连接,则这些删除的边称为图形的割集。
示例
看下图。其切割集为E1={e1,e3,e5,e8}。
从图形中删除切割集E1后,它将显示如下-
类似地,还有其他切割集可以断开图形-
E3={e9}–图形的最小割集。
E4={e3,e4,e5}