图的割点与连通性

在图论中，割点（Cut Vertex）是指当且仅当移除某个顶点及其所有相关边后，原图会分裂成两个或更多个互不相连的部分，即这些部分之间不再存在路径相互连接。理解割点有助于分析图的连通性和结构稳定性等问题。

割点的基本概念

给定一个无向图 ( G = (V, E) )，其中 ( V ) 表示顶点集合，( E ) 表示边集合。我们定义如果移除某个顶点 ( v \in V ) 以及与其相连的所有边后，图 ( G ) 分裂成多个连通分量，则称该顶点为割点。

检测割点的方法

Tarjan 算法

Tarjan 算法是一种高效的检测割点和桥（Cut Edge）的算法。其核心思想是通过深度优先搜索（DFS），结合使用低点数组来确定每个顶点是否为割点。

详细步骤如下：

初始化：对图进行 DFS 遍历，同时维护一个时间戳数组 ( \text{time} )，记录每个顶点第一次被访问的时间。
递归搜索：
- 当访问到顶点 ( v ) 时，将其标记为已访问，并将时间戳设置为其当前值（即 ( \text{time}[v] = t )）。
- 对于每一个未访问过的邻接节点 ( u )，进行递归调用。
- 更新低点值：如果子树 ( T_u ) 的最小出口节点 ( L[u] \leq v )，则顶点 ( v ) 是割点（( v ) 和其所有子节点构成的连通分量是一个独立部分）。
回溯更新：
- 当递归调用返回后，检查是否可以跳过父节点进行回溯。如果存在一个子节点 ( u )，使得 ( L[u] \geq v ) 且 ( v ) 是根节点或非叶节点，则说明存在从 ( v ) 指向其他连通分量的路径。

具体代码实现

def find_cut_vertices(graph):
    def dfs(v, parent, visited, time, low, cut_points):
        nonlocal timestamp
        visited[v] = True
        time[v] = low[v] = timestamp
        timestamp += 1
        
        children = 0
        for neighbor in graph[v]:
            if not visited[neighbor]:
                children += 1
                dfs(neighbor, v, visited, time, low, cut_points)
                low[v] = min(low[v], low[neighbor])
                
                # 判断是否为割点
                if parent == -1 and children > 1:
                    cut_points.append(v)
                elif parent != -1 and low[neighbor] >= time[v]:
                    cut_points.append(v)
            elif neighbor != parent:
                low[v] = min(low[v], time[neighbor])
    
    n = len(graph)
    visited = [False] * n
    time = [-1] * n  # 记录时间戳
    low = [0] * n    # 记录低点值
    cut_points = []
    
    for i in range(n):
        if not visited[i]:
            dfs(i, -1, visited, time, low, cut_points)
    
    return cut_points

# 示例图
graph = {
    0: [1, 2],
    1: [0, 3, 4],
    2: [0, 5],
    3: [1],
    4: [1, 5],
    5: [2, 4]
}

cut_vertices = find_cut_vertices(graph)
print("Cut vertices:", cut_vertices)

图的连通性

图 ( G ) 的连通性可以通过分析其割点来衡量。如果移除某个顶点及其相关边后，图分裂成多个连通分量，则说明该顶点是关键节点，对图的整体结构有着重要影响。

连通度与割点的关系

2-连通图：一个无向图 ( G ) 称为 2-连通的当且仅当它没有割点。也就是说，在 2-连通图中，不存在单一节点移除导致图分裂的现象。
k-连通图（( k > 2 )）：更多情况下，考虑更高阶的连通度时会引入桥的概念。

通过检测和理解这些关键顶点及其影响，可以在实际应用中更有效地设计网络或系统，以提高其稳定性和可靠性。