Vertex Articulation Point
A vertex articulation point (or cut vertex) is a vertex whose removal would disconnect the graph or increase the number of connected components. Detecting articulation points allows identifying critical nodes.
Some key aspects:
- Removal of articulation point disconnects graph
- Points whose removal increases connected components count
- Can be detected using DFS tree properties
Java example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
| boolean[] findArtPoints(Graph graph) {
int V = graph.V;
boolean[] visited = new boolean[V];
int[] disc = new int[V];
int[] low = new int[V];
boolean[] art = new boolean[V];
for (int u = 0; u < V; u++) {
if (!visited[u]) {
DFS(u, visited, disc, low, art);
}
}
return art;
}
void DFS(int u, boolean[] visited, int[] disc, int[] low, boolean[] art) {
visited[u] = true;
disc[u] = low[u] = ++time;
// Check if articulation point using DFS tree
}
|
C++ example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
| vector<bool> findArtPoints(Graph graph) {
int V = graph.V;
vector<bool> visited(V, false);
vector<int> disc(V);
vector<int> low(V);
vector<bool> art(V, false);
for (int u = 0; u < V; u++) {
if (!visited[u]) {
DFS(u, visited, disc, low, art);
}
}
return art;
}
void DFS(int u, vector<bool>& visited, vector<int>& disc,
vector<int>& low, vector<bool>& art) {
// DFS to find cut vertices
}
|
Python example:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
| def find_articulation_points(graph):
visited = [False] * len(graph)
disc = [0] * len(graph)
low = [0] * len(graph)
art = [False] * len(graph)
# Run DFS
return [i for i, is_art in enumerate(art) if is_art]
def dfs(node, visited, disc, low, art):
visited[node] = True
# DFS to find cut vertices
|
Articulation points help identify critical nodes whose removal breaks connectivity. Useful in network reliability.
In graph theory, a vertex is called an articulation point if its removal increases the number of connected components in the graph. In other words, it’s a vertex that, if removed along with associated edges, makes the graph more disconnected. Articulation points are crucial in network design, as their failure could fragment the network.
Let’s consider a simple undirected graph with 5 nodes labeled 0 to 4.
0
/ \
/ \
1-----2
| |
4-----3
In this graph, if we remove the vertex 0, the graph remains connected. However, if we remove the vertex 1, the graph becomes disconnected; it splits into two subgraphs: one containing {0, 2, 3, 4} and another isolated vertex 1.
Thus, vertex 1 is an articulation point.
The process of identifying articulation points using DFS involves assigning a “discovery time” and a “low value” to each vertex.
- Discovery time (
disc): The time at which a vertex is first discovered in the DFS traversal. - Low value (
low): The smallest disc reachable from that vertex (including itself).
For vertex u, if there exists a vertex v such that low[v] >= disc[u], then u is an articulation point. This basically says that v and its descendants in the DFS tree cannot reach a vertex higher up than u.
Here’s how disc and low arrays could look for this example:
Vertex: 0 1 2 3 4
disc[]: 1 2 3 4 5
low[]: 1 2 1 1 1
The algorithm starts from a root vertex (say vertex 0), and it applies DFS to traverse and find the articulation points.
Understanding the disc and low arrays will make the code implementation in Java, C++, and Python much clearer.
A vertex articulation point in a graph is a node that, if removed along with its incident edges, would increase the number of connected components in the graph. In simpler terms, it’s a critical point that provides the only path between different parts of the graph.
Visual Representation:
Let’s take a simple undirected graph with vertices (A, B, C, D, E, F).
A-------B
| |
| |
D-------C
| |
| |
E-------F
In this graph, vertex (C) and (D) are articulation points.
Verification Steps:
Remove vertex (C), you get two disconnected subgraphs: ( {A, B} ) and ( {D, E, F} ).
Remove vertex (D), you get two disconnected subgraphs: ( {A, B, C} ) and ( {E, F} ).
Any other vertex, if removed, won’t break the graph into multiple disconnected components.
Vertex articulation points are crucial in network design and various algorithms. Identifying them can help in understanding network vulnerabilities, as losing such a point could break the network into isolated segments.
Solution
We can identify articulation points using Depth First Search (DFS). Below are implementations in Java, C++, and Python to find articulation points in an undirected graph.
Java
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
| import java.util.*;
public class ArticulationPoint {
static int time = 0;
static void dfs(List<Integer>[] graph, boolean[] visited, int[] disc, int[] low, int u, int parent, List<Integer> points) {
visited[u] = true;
disc[u] = low[u] = ++time;
int children = 0;
for (int v : graph[u]) {
if (!visited[v]) {
children++;
dfs(graph, visited, disc, low, v, u, points);
low[u] = Math.min(low[u], low[v]);
if (low[v] >= disc[u] && parent != -1) {
points.add(u);
}
} else if (v != parent) {
low[u] = Math.min(low[u], disc[v]);
}
}
if (parent == -1 && children > 1) {
points.add(u);
}
}
public static void main(String[] args) {
int n = 5;
List<Integer>[] graph = new ArrayList[n];
for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
graph[0].add(1);
graph[1].add(0);
graph[1].add(2);
graph[2].add(1);
graph[2].add(0);
graph[0].add(2);
graph[0].add(3);
graph[3].add(0);
graph[3].add(4);
graph[4].add(3);
boolean[] visited = new boolean[n];
int[] disc = new int[n];
int[] low = new int[n];
List<Integer> points = new ArrayList<>();
dfs(graph, visited, disc, low, 0, -1, points);
System.out.println("Articulation Points: " + points);
}
}
|
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
| #include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
vector<int> findArticulationPoints(vector<vector<int>> &graph) {
int n = graph.size();
vector<int> low(n), disc(n), parent(n, -1);
vector<bool> visited(n, false);
vector<int> points;
int time = 0;
function<void(int)> dfs = [&](int u) {
visited[u] = true;
disc[u] = low[u] = ++time;
int children = 0;
for (int v : graph[u]) {
if (!visited[v]) {
parent[v] = u;
children++;
dfs(v);
low[u] = min(low[u], low[v]);
if (low[v] >= disc[u] && parent[u] != -1) {
points.push_back(u);
}
} else if (v != parent[u]) {
low[u] = min(low[u], disc[v]);
}
}
if (parent[u] == -1 && children > 1) {
points.push_back(u);
}
};
dfs(0);
return points;
}
int main() {
vector<vector<int>> graph = {{1, 2, 3}, {0, 2}, {0, 1}, {0, 4}, {3}};
vector<int> points = findArticulationPoints(graph);
cout << "Articulation Points: ";
for (int point : points) {
cout << point << " ";
}
cout << endl;
}
|
Python
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
| def find_articulation_points(graph):
n = len(graph)
low = [0] * n
disc = [0] * n
parent = [-1] * n
visited = [False] * n
points = []
time = 0
def dfs(u):
nonlocal time
visited[u] = True
disc[u] = low[u] = time + 1
time += 1
children = 0
for v in graph[u]:
if not visited[v]:
parent[v] = u
children += 1
dfs(v)
low[u] = min(low[u], low[v])
if low[v] >= disc[u] and parent[u] != -1:
points.append(u)
elif v != parent[u]:
low[u]
= min(low[u], disc[v])
if parent[u] == -1 and children > 1:
points.append(u)
dfs(0)
return points
graph = [[1, 2, 3], [0, 2], [0, 1], [0, 4], [3]]
points = find_articulation_points(graph)
print("Articulation Points:", points)
|
Key Takeaways
- The Depth First Search (DFS) algorithm is an effective way to find articulation points.
- The “low” and “disc” arrays are used to keep track of the lowest reachable vertex and the discovery time of each vertex, respectively.
- Java, C++, and Python code implementations follow the same logic but differ in syntax and data structures.