图论中的割点

2025年7月12日 | 阅读8分钟

如果我们想了解割顶，那么我们必须先了解连通性。之后，我们才能更好地理解割顶。

连接性

图的连通性用于表示图是连通还是不连通。所以，在连通性方面，图要么是连通的，要么是不连通的。如果一个连通图包含一些路径可以从任意一个顶点遍历到其他任何一个顶点，那么它就被称为图的连通性。

如果图中任意一对顶点之间都存在路径，则该图被认为是连通的。如果图中存在多个不连通的顶点和边，则该图被认为是断开的。如果我们想知道是否可以从图中的一个顶点遍历到另一个顶点，那么我们可以通过查看图是如何连接的来做到这一点。

割顶

割顶可以描述为图中的一个顶点，移除该顶点后会使图断开。割顶还有一个名字，即割点。如果从图中移除一个顶点，由于这个原因，图会分裂成两个或两个以上的图，那么这种图就被称为割顶。假设我们有一个连通图G。如果图G包含一个顶点x，那么它可以被称为割顶。

如果我们从图中移除这个顶点（G-x），并因此导致图断开。当我们删除图中的一个顶点时，所有连接到该顶点的边也会被删除。如果一个连通图存在，那么它最多可以包含（n-2）个割顶。

割顶用于增加图中的连通分量数量。如果我们想了解网络的脆弱性和可靠性，在这种情况下，割顶起着至关重要的作用，因为它们是其故障会导致网络断开的点。因此，割顶会影响流量或通信。我们可以通过下面的例子来理解割顶：

该图共有11个顶点。在所有顶点中，顶点0和顶点2是割顶。当我们从上图中移除顶点'0'时，就没有路径可以从9、7到达3和1。类似地，当我们从上图中移除顶点'2'时，就没有路径可以从3、1到达4、6，反之亦然。如果我们移除这两个顶点之外的任何顶点，那么就有一条路径可以让我们到达所有其他顶点。因此，该图的割顶是（0, 2）。

移除割顶“0”后的图如下所示：

移除割顶“2”后的图如下所示：

割顶的性质

割顶有很多性质，其中一些如下所示：

图中可以存在多个割顶。识别图中的割顶有助于发现网络中的脆弱点。
当我们从图中删除一个割顶时，所有最初连接到该割顶的顶点都会变得孤立，因此图会断开。
割顶在许多应用中都可以使用，例如交通网络、网络设计和社交网络。在所有这些应用中，网络连通性都至关重要。
我们不仅在理论图中使用割顶，还有各种实际应用可以使用割顶，例如在通信网络中寻找关键基础设施，以及这类连通性对于维护连通性至关重要。
我们有各种算法可以用来有效地找到所有的割顶，这些算法可以使用深度优先搜索（DFS）。这些算法用于分析和加强网络可靠性。

割顶的用途

网络可靠性和脆弱性：如果我们想了解网络可靠性，在这种情况下，割顶起着非常重要的作用，因为它们是其故障会导致网络断开的点。当我们从图中移除一个割顶时，所有先前连接的组件都会变得孤立。借助这一点，我们可以设计出更具弹性的网络。为此，我们必须找到并加强这些关键点，以确保即使某些顶点发生故障，整个网络也能正常工作。

改进基础设施：在实际应用中找到割顶时，它对基础设施改进有重大影响。如果我们能够识别交通或通信网络中的这些关键点，规划者就可以实施替代路由策略或冗余措施。我们可以通过一个例子来理解这一点。

假设我们在数据网络中有一个服务器，如果这个服务器成为一个割顶，那么在发生意外故障或维护时，它可能会阻止服务中断，因为有替代路径或备用服务器。这种方法可以用来增强整体网络可靠性，也用于确保持续的服务交付。

割顶与桥的区别

有一些要点用于区分割顶和桥，它们描述如下：

利用割顶和桥梁来维持图的连通性至关重要，但它们影响的对象不同。当我们移除一个割顶时，它会直接影响顶点的连接以及图的连通性，从而导致子图不相交。

与此同时，在桥的情况下，重点在于边。当我们移除桥或图中的一条边时，由于这个原因，图的一部分断开了，但这种移除不会影响顶点本身。通过理解割顶和桥，我们可以评估网络中存在的不同类型的脆弱性。

割顶的例子

在割顶的情况下有各种各样的例子，其中一些如下所示：

示例 1

这个例子包含一个图，我们需要找到这个图的割顶。

解答：该图共有6个顶点。在所有顶点中，顶点3是一个割顶，因为如果我们从该图中移除它，就没有路径可以到达图中其他顶点，如4、5和6。因此，通过删除顶点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：本例包含一个图，我们需要找到该图的割顶。

解答：该图共有8个顶点。在所有顶点中，顶点c和顶点e是割顶。当我们从该图中移除顶点e时，就没有路径可以从顶点c到达顶点（f、h）。类似地，当我们从该图中移除顶点c时，就没有路径可以从顶点（b、d）到达顶点e，反之亦然。

因此，通过删除顶点e或顶点c中的任何一个，图都会断开。如果我们移除这两个顶点以外的任何顶点，那么就有一条路径可以让我们到达所有其他顶点。因此，该图的割顶是（c、e）。

移除割顶“c”后的图如下所示：

移除割顶“e”后的图如下所示：

示例 4

这个例子包含一个图，我们需要找到这个图的割顶。

解答：该图共有7个顶点。在所有顶点中，顶点6是一个割顶，因为如果我们从该图中移除它，就没有路径可以从顶点1到达顶点3或顶点7，反之亦然。因此，通过删除顶点6，图将断开。如果我们移除顶点6以外的任何顶点，我们总会得到一条路径，可以到达所有其他顶点。因此，该图的割顶是6。移除割顶后的图如下所示：