04 Connectivity, Articulation Points, Bridges, Block Decomposition

Measuring Connectivity: Beyond Simple Connectedness

While the basic notion of graph connectedness tells us whether there is a path between any two vertices, it does not capture the degree of connectivity, or how robustly connected a graph is. In many scenarios, we need to quantify how “well-connected” a graph is, for example, to assess its resilience to vertex or edge removals. This leads us to more refined measures of connectivity, such as k-connectivity and k-edge-connectivity.

k-Vertex Connectivity

A graph $G = (V, E)$ is said to be k-vertex-connected (or simply k-connected) if it remains connected even after removing any set of fewer than $k$ vertices. Formally, a graph $G$ with $∣ V ∣ \geq k + 1$ vertices is k-connected if for every set $X \subseteq V$ with $∣ X ∣ < k$ , the subgraph $G [V ∖ X]$ is still connected.

The notion of k-connectivity quantifies the minimum number of vertices that need to be removed to disconnect the graph. Higher values of $k$ indicate stronger connectivity. A graph is 1-connected if and only if it is connected in the standard sense. A graph is 2-connected if it remains connected even after removing any single vertex.

Separators and Articulation Points

Vertex Separator (or k-Separator): A set of vertices $X \subseteq V$ is called a vertex separator or simply separator if removing $X$ disconnects the graph, i.e., $G [V ∖ X]$ is not connected. If $∣ X ∣ = k$ , it is a k-separator.
u-v Separator: For two vertices $u, v \in V$ , a u-v separator is a set of vertices $X \subseteq V ∖ {u, v}$ such that in $G [V ∖ X]$ , vertices $u$ and $v$ belong to different connected components.
Articulation Point (or Cut Vertex): An articulation point or cut vertex is a vertex $v$ whose removal increases the number of connected components in the graph. In other words, $G - v$ is disconnected.

A graph $G$ is k-connected if and only if every vertex separator has size at least $k$ . Equivalently, for any two non-adjacent vertices $u, v \in V$ , every $u - v$ separator has size at least $k$ .

k-Edge Connectivity

Analogously, we can define k-edge-connectivity. A graph $G = (V, E)$ is k-edge-connected if it remains connected even after removing any set of fewer than $k$ edges. Formally, a graph $G$ is k-edge-connected if for every set $X \subseteq E$ with $∣ X ∣ < k$ , the graph $(V, E ∖ X)$ is still connected.

k-edge-connectivity quantifies the minimum number of edges that need to be removed to disconnect the graph. A graph is 1-edge-connected if and only if it is connected.

Edge Separator (or k-Edge Separator)

Edge Separator (or k-Edge Separator): A set of edges $X \subseteq E$ is called an edge separator if removing $X$ disconnects the graph, i.e., $(V, E ∖ X)$ is not connected. If $∣ X ∣ = k$ , it is a k-edge separator.
u-v Edge Separator: For two vertices $u, v \in V$ , a u-v edge separator is a set of edges $X \subseteq E$ such that in $(V, E ∖ X)$ , vertices $u$ and $v$ are in different connected components.

A graph $G$ is k-edge-connected if and only if every edge separator has size at least $k$ . Equivalently, for any two vertices $u, v \in V$ , every $u - v$ edge separator has size at least $k$ .

Menger’s Theorem

A cornerstone result in connectivity theory is Menger’s Theorem (Satz 1.25), which establishes a deep connection between vertex/edge separators and the number of disjoint paths.

Theorem 1.25 (Menger’s Theorem): Let $G = (V, E)$ be a graph and $u, v \in V, u \neq = v$ . Then:

(a) The minimum size of a $u - v$ vertex separator is equal to the maximum number of internally vertex-disjoint $u - v$ paths. (Vertex-disjoint paths are internally vertex-disjoint if they share no common vertices other than $u$ and $v$ .)
(b) The minimum size of a $u - v$ edge separator is equal to the maximum number of edge-disjoint $u - v$ paths. (Edge-disjoint paths are edge-disjoint if they share no common edges.)

Menger’s Theorem is a powerful duality result that bridges the concept of separation (vertex/edge separators) and connection (disjoint paths). It has profound implications in network reliability, flow theory, and combinatorial optimization. The proof of Menger’s Theorem is deferred to a later section (3.1.2), where we will have developed the necessary tools from network flow theory to tackle it effectively.

Articulation Points: Identifying Vulnerable Vertices (1.4.1)

Articulation points are critical vertices in a graph, as their removal can fragment the graph into multiple disconnected components. Identifying articulation points is essential in network design, vulnerability analysis, and understanding graph structure.

Depth-First Search (DFS) for Articulation Points

Depth-first search (DFS) provides an efficient algorithm for finding articulation points in a connected graph. By augmenting DFS with additional bookkeeping, we can identify articulation points during a single DFS traversal.

The core idea is to use DFS numbers (discovery times) and low-link values to detect vertices whose removal disconnects the graph. The low-link value $l o w [v]$ of a vertex $v$ is the smallest DFS number reachable from $v$ by following tree edges and at most one back-edge in the DFS tree.

Algorithm: DFS-Visit (for Articulation Points)

Algorithm: DFS-Visit(G, v)
Input: Graph G, vertex v
Output: Low-link value of v (and marks articulation points)
 
num = num + 1
dfs[v] = num
low[v] = dfs[v]
isArtVert[v] = false  // Initially not an articulation point
 
for each neighbor w of v:
    if dfs[w] == 0: // w is unvisited (tree edge)
        T = T ∪ { {v, w} }  // Add {v, w} to DFS tree
        val = DFS-Visit(G, w) // Recursive call for w
        if val ≥ dfs[v]:
            isArtVert[v] = true // v is articulation point
        low[v] = min(low[v], val)
    else if w is not parent of v in DFS tree: // back-edge
        low[v] = min(low[v], dfs[w])
 
return low[v]

Algorithm: DFS (for Articulation Points)

Algorithm: DFS(G, s)
Input: Graph G, starting vertex s
Output: Articulation points marked in isArtVert array
 
for each vertex v ∈ V:
    dfs[v] = 0 // Initialize DFS numbers
num = 0
T = Ø // Initialize DFS tree edges
DFS-Visit(G, s)
 
if s has at least two children in DFS tree T:
    isArtVert[s] = true // Start vertex special case
else:
    isArtVert[s] = false

Theorem 1.27: For a connected graph $G = (V, E)$ , the DFS-based algorithm correctly identifies all articulation points in $O (∣ E ∣)$ time.

The algorithm efficiently computes DFS numbers and low-link values in a single DFS traversal, allowing for linear-time detection of articulation points. The special case for the starting vertex of DFS needs to be handled separately.

Bridges: Critical Edges (1.4.2)

Just as articulation points are critical vertices, bridges are critical edges whose removal disconnects the graph. An edge $e \in E$ in a connected graph $G = (V, E)$ is called a bridge if $G - e = (V, E ∖ {e})$ is disconnected.

Bridges represent essential connections in a graph, and their identification is important in network analysis and robustness assessment.

DFS for Bridges

Similar to articulation points, bridges can also be efficiently detected using DFS. For a DFS tree edge $(v, w)$ , where $v$ is the parent of $w$ , the edge ${v, w}$ is a bridge if and only if $l o w [w] > df s [v]$ . This condition can be checked during the DFS traversal, allowing for linear-time bridge detection.

Theorem 1.28: For a connected graph $G = (V, E)$ , articulation points and bridges can be computed in $O (∣ E ∣)$ time using DFS.

Block Decomposition: Decomposing Graphs into 2-Connected Components (1.4.3)

The concept of blocks provides a way to decompose a graph into its 2-connected components. A block is a maximal 2-connected subgraph. Blocks represent the “indivisible” 2-connected units of a graph.

Definition/Proposition 1.29: For edges $e, f \in E$ , define a relation $e \sim f$ if $e = f$ or there is a cycle containing both $e$ and $f$ . This relation is an equivalence relation, and its equivalence classes are called blocks.

The blocks of a graph can be organized into a tree structure called the block-cut tree. This tree represents the hierarchical relationship between blocks and articulation points in the graph, providing a valuable tool for understanding graph structure and decomposition.

By identifying articulation points and blocks, we gain deeper insights into graph connectivity and can decompose complex graphs into simpler, more manageable components for further analysis. The algorithms based on DFS provide efficient means for computing these connectivity-related properties.

Prev: 03 Shortest Paths | Next: 05 Cycles, Euler Tours, Hamiltonian Cycles, Traveling Salesman Problem

CS Notes

Explorer