图论中的割集

如果我们想学习割集，那么我们必须先学习连通性、割点和割边。只有这样，我们才能正确理解割集。

连接性

如果我们想知道能否从图的一个顶点遍历到另一个顶点，那么我们可以通过查看图是如何连接的来做到这一点。连通性可以被描述为图论领域的一个基本概念。借助连通性，可以很容易地定义图是连通的还是不连通的。

如果一个图包含每对顶点之间的路径，那么这种图就称为连通图。如果一个 连通图 包含一些路径可以从每个顶点遍历到任何其他顶点，那么它就被称为图的连通性。如果一个图包含多个不连通的顶点和边，那么这种图就称为不连通图。

割点

割点还有一个名字，即 关节点。假设我们有一个连通图 G。如果图 G 包含一个顶点 x，那么它可以被称为割点。如果我们从图中删除这个顶点（G-x），并且由于这个删除，图变得不连通。

换句话说，割点可以被描述为一个顶点，将其从图中删除会使图分解成两个或更多个图。当从图中删除一个顶点时，与该顶点相连的所有边也会被删除。如果一个图是连通的，那么它最多可以包含 (n-2) 个割点。

割点示例

割点包含很多例子，其中一些如下所示

示例 1

这个例子包含一个有向图，我们需要找出这个图的割点。

解： 该图有 6 个顶点。在所有顶点中，顶点 3 是割点，因为如果我们从上面的图中删除顶点 '3'，就没有办法到达 1、2 和 4。因此，删除顶点 3 后，图将变得不连通。如果我们删除除顶点 3 之外的任何顶点，则总会有一条路径可以到达所有其他顶点。因此，此图的割点是 3。删除割点后的图如下所示

示例 2

这个例子包含一个有向图，我们需要找出这个图的割点。

解： 如果我们删除上面的图中的两个顶点 y 和 q，只有这样我们才能断开上面的图。当我们从上面的图中删除顶点 'y' 时，就没有办法从 x、z 到达 r、s 和 t。删除 'y' 后，如果我们从上面的图中删除 'q'，那么就没有办法从 x、z 到达 p、r、s 和 t，反之亦然。

如果我们只删除一个顶点，那么这个图将不会不连通。我们需要删除两个顶点（y、q）才能断开图。如果我们删除除这两个顶点之外的任何顶点，则总会有一条路径可以到达所有其他顶点。因此，此图的割点是（y、q）。删除割点后的图如下所示

示例 3

这个例子包含一个有向图，我们需要找出这个图的割点。

解： 该图有 5 个顶点。在所有顶点中，顶点 4 是割点，因为如果我们从上面的图中删除顶点 '4'，就没有办法到达顶点 2、3 和 5。因此，删除顶点 4 后，图将变得不连通。如果我们删除除顶点 4 之外的任何顶点，则总会有一条路径可以到达所有其他顶点。因此，此图的割点是 4。删除割点后的图如下所示

示例 4

这个例子包含一个有向图，我们需要找出这个图的割点。

解： 如果我们删除上面的图中的两个顶点 z 和 q，只有这样我们才能断开上面的图。如果我们从上面的图中删除顶点 'z'，那么仍然有一条路径可以到达其他顶点。但是删除顶点 'z' 后，如果我们从上面的图中删除 'q'，那么就没有办法到达 r、s 和 t。

如果我们只删除一个顶点，那么这个图将不会不连通。我们需要删除两个顶点（z、q）才能断开图。如果我们删除除这两个顶点之外的任何顶点，则总会有一条路径可以到达所有其他顶点。因此，此图的割点是（z、q）。删除割点后的图如下所示

割边

割边还有另一个名字，即桥。假设我们有一个连通图 G。如果该图包含一条边 'e'，它可以被称为割边，如果我们从图中删除这条边（G-e），并且由于这次删除，图变得不连通。换句话说，割边可以被描述为一条边，将其从图中删除会使图分解成两个或更多个图。如果一个图是连通的，那么它最多可以包含 (n-1) 条割边。

割边示例

割边包含很多例子。其中一些如下所示

示例 1

这个例子包含一个有向图，我们需要找出这个图的割边。

解： 该图有 4 条边。在所有边中，边 yz 或 yp 是割边，因为如果我们从上面的图中删除边 'yz' 或 'yp'，就没有办法到达顶点 x 和 z 或顶点 p。因此，通过删除边 yz 或 yp，图将变得不连通。如果我们删除除 yz 或 yp 之外的任何边，则总会有一条路径可以到达所有其他顶点。因此，此图的割边是 yz 或 yp。删除割边 'yz' 后的图如下所示

删除割边 'yp' 后的图如下所示

示例 2

这个例子包含一个有向图，我们需要找出这个图的割边。

解： 该图有 10 条边。在所有边中，边 'zq' 是割边，因为如果我们从上面的图中删除边 'zq'，就没有办法从 x、y、p、z 到达 r、s 和 t。因此，通过删除边 'zq'，图将变得不连通。如果我们删除除 'zq' 之外的任何边，则总会有一条路径可以到达所有其他顶点。因此，此图的割边是 zq。删除割边后的图如下所示

示例 3

这个例子包含一个有向图，我们需要找出这个图的割边。

解： 如果我们删除上面的图中的两条边 'xz' 和 'yz'，只有这样我们才能断开上面的图。如果我们从上面的图中删除边 'xz'，那么仍然有一条路径可以到达其他顶点。但是删除边 'xz' 后，如果我们从上面的图中删除 'yz'，那么就没有办法从顶点 x 和 y 到达顶点 p 和 q。

如果我们只删除一条边，那么这个图将不会不连通。我们需要删除两条边（'xz'、'yz'）才能断开图。如果我们删除除这两条边之外的任何边，那么总会有一条路径可以到达所有其他边。因此，此图的割边是（'xz' 和 'yz'）。删除割边后的图如下所示

注意：如果一个连通图包含 n 个顶点，那么割边包含一些性质，如下所述

• 如果图 G 中存在一条边 e，它不是任何环的一部分，那么它包含一条割边 e ∈ G。
• 在连通图的情况下，最多可以有 n-1 条割边。
• 如果图中存在割边，那么图中也一定存在割点，因为割边至少有一个顶点是割点。
• 如果图中存在割点，那么不一定图中也存在割边。但是如果存在割边，那么一定存在割点。

割集

假设我们有一个连通图 G。如果该图包含边 E 的子集 E`，那么这个子集被称为割集，如果我们删除子集中的所有边（G-E`），并且由于这次删除，图变得不连通。换句话说，割集可以被描述为一组边，将其从图中删除会使图分解成两个或更多个图。假设有一个连通图 G，它包含边集 E，那么为了成为割集，需要满足一些性质，如下所示

• 如果我们删除集合 S 的所有边，并且这次删除断开了图 G。
• 如果我们删除集合 S 的一部分边（但不是全部），那么这次删除不会断开图 G。

割集示例

割集包含很多例子。其中一些如下所示

示例 1

这个例子包含一个有向图，我们需要找出这个图的割集。

解： 在这个图中，我们创建了一个边集 E1 = {1, 3, 5, 8}。如果我们从上面的图中删除这个集合 E1 的所有边，只有这样我们才能断开上面的图。如果我们从集合 E1 中留下任何一条边，那么图就不会断开。如果我们从上面的图中删除边 '1'，那么仍然有一条路径可以到达其他顶点。

删除所有边后，图被分成 2 部分。为了断开图，应删除 E1 的所有边。因此，此图的割集 E1 = {1, 3, 5, 8}。删除割集 E1 后的图如下所示

同样，上面的图可以包含更多割集，将图分成多个部分。这些割集可以是 E2 = {9}，E3 = {3, 4, 5}。删除割集 E2 后的图如下所示

删除割集 E3 后的图如下所示

示例 2

这个例子包含一个有向图，我们需要找出这个图的割集。

解： 在这个图中，我们创建了一个边集 E1 = {yp, yq, zq}。如果我们从上面的图中删除这个集合 E1 的所有边，只有这样我们才能断开上面的图。如果我们从集合 E1 中留下任何一条边，那么图就不会断开。如果我们只删除两条边 'yp 和 yq'，那么图就无法断开。

删除所有边后，图被分成 2 部分。为了断开图，应删除 E1 的所有边。因此，此图的割集 E1 = {yp, yq, zq}。删除割集 E1 后的图如下所示

同样，上面的图可以包含更多割集，将图分成多个部分。这些割集可以是 E2 = {pr, qs}，E3 = {rt}。删除割集 E2 后的图如下所示

删除割集 E3 后的图如下所示

示例 3

这个例子包含一个有向图，我们需要找出这个图的割集。

解： 在这个图中，我们创建了一个边集 E1 = {x, y, z}。如果我们从上面的图中删除这个集合 E1 的所有边，只有这样我们才能断开上面的图。如果我们从集合 E1 中删除任何一条边，那么图就不会断开。为了断开图，应删除 E1 的所有边。删除所有边后，图被分成 2 部分。因此，此图的割集 E1 = {x, y, z}。删除割集 E1 后的图如下所示

同样，上面的图可以包含更多割集，将图分成多个部分。这些割集可以是 E2 = {x, r, s}，E3 = {x, y, r}。删除割集 E2 后的图如下所示

删除割集 E3 后的图如下所示

示例 4

这个例子包含一个有向图，我们需要找出这个图的割集。

解： 在这个图中，我们创建了一个边集 E1 = {E2, E3, E5, E6}。如果我们从上面的图中删除这个集合 E1 的所有边，只有这样我们才能断开上面的图。为了断开图，应删除 E1 的所有边。如果我们从集合 E1 中删除任何一条边，那么图就不会断开。删除所有边后，图被分成 2 部分。因此，此图的割集 E1 = {E2, E3, E5, E6}。删除割集 E1 后的图如下所示

同样，上面的图可以包含更多割集，将图分成多个部分。这些割集可以是 E2 = {E5, E6, E7, E8}，等等。删除割集 E2 后的图如下所示