图的割集和割顶点
是否可以从一个顶点到另一个顶点遍历图取决于图的连接方式。连接性是图论中的一个基本概念。连接性定义图形是已连接还是已断开。
连接性
如果每对顶点之间都有一条路径，则称该图是连通的。从每个顶点到任何其他顶点，都应该有一些遍历的路径。这称为图的连通性。具有多个不连续的顶点和边的图形被称为不连续的。
切顶点
令“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}