图论 - 连通性
能否从一个顶点遍历到另一个顶点取决于图的连接方式。连通性是图论中的一个基本概念。连通性定义了图是连通的还是不连通的。它根据边和顶点有子主题，称为边连通性和顶点连通性。让我们详细讨论一下。
连通性
如果每对顶点之间存在一条路径，则称该图是连通的。从每个顶点到任何其他顶点，都应该存在一些路径可以遍历。这就是所谓的图的连通性。具有多个不连通顶点和边的图被称为不连通图。
示例1
在下面的图中，可以从一个顶点移动到任何其他顶点。例如，可以使用路径“a-b-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