图论 - 连接性
是否可以将图从一个顶点遍历到另一个顶点取决于图的连接方式。连接性是图论中的一个基本概念。连接性定义了图是连接的还是断开的。它具有基于边和顶点的子主题，称为边连接性和顶点连接性。让我们详细讨论它们。
连接性
如果每对顶点之间都有路径，则称图是连通的。从每个顶点到任何其他顶点，都应该有一些路径可以遍历。这就是所谓的图的连通性。具有多个断开的顶点和边的图称为断开的。
实施例1
在下图中，可以从一个顶点移动到任何其他顶点。例如，可以使用路径“ab-e”从顶点“a”遍历到顶点“e”。
实施例2
在以下示例中，从顶点“a”遍历到顶点“f”是不可能的，因为它们之间没有直接或间接的路径。因此它是一个断开连接的图。
剪切顶点
令“G”为连通图。如果“G-V”（从“G”中删除“V”）导致断开图，则顶点 V ∈ G 称为“G”的割顶点。从图中删除切割顶点会将其分成两个或更多图。
注意- 删除切割顶点可能会导致图形断开连接。
连通图“G”最多可以有 (n–2) 个割点。
例子
在下图中，顶点“e”和“c”是切割顶点。
通过删除“e”或“c”，该图将成为断开连接的图。
如果没有“g”，顶点“c”和顶点“h”以及许多其他顶点之间就没有路径。因此，它是一个断开的图，割点为“e”。类似地，“c”也是上图的切割顶点。
切边（桥）
令“G”为连通图。如果“G-e”导致断开的图，则边“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}
边缘连接
令“G”为连通图。删除使“G”断开的边的最小数量称为 G 的边连通性。
符号- λ(G)
换句话说，G的最小割集中的边的数量称为G的边连通性。
如果“G”有切边，则 λ(G) 为 1。（G 的边连通性。）
例子
看一下下图。通过删除两条最小边，连通图就会断开。因此，其边缘连通性 (λ(G)) 为 2。
以下是通过删除两条边来断开图形的四种方法 -
顶点连接
令“G”为连通图。删除使“G”断开或将“G”简化为平凡图的顶点的最小数量称为其顶点连通性。
符号- K(G)
例子
在上图中，删除顶点“e”和“i”会使图断开连接。
如果 G 有割顶点，则 K(G) = 1。
符号- 对于任何连通图 G，
K(G) ≤ λ(G) ≤ δ(G)
顶点连通性 (K(G))、边连通性 (λ(G))、G 的最小度数 (δ(G))。
例子
计算下图的 λ(G) 和 K(G) -
解决方案
从图中可以看出，
δ(G) = 3
K(G) ≤ λ(G) ≤ δ(G) = 3 (1)
K(G)≥2 (2)
删除边{d，e}和{b，h}，我们可以断开G。
所以，
λ(G) = 2
2 ≤ λ(G) ≤ δ(G) = 2 (3)
由(2)和(3)可知，顶点连通性K(G) = 2