- The connectivity of a graph is the smallest number of vertices that need tobe deleted to disconnect the graph.
- If the graph has an articulation vertex, the connectivity is 1. More robustgraphs that don't have a single point of failure/articulation vertex aresaid to be binconnected.
- To test for an articulation vertex by brute force, delete each vertex,and check if the graph has disconnected into components. this is O(V(V+E)) time.
Joke: an articulate vertex is one that speaks very well, and is thus important to the functioning of the graph. If it is killed, it will disconnect society, as there is no one to fulfil its ability to cross barriers with its eloquent speech.
§ Articulation vertices on the DFS tree - undirected
- If we think of only the DFS tree for a moment of an undirected graph and ignore all other edges, thenall interneal non-leaf vertices become articulation vertices, because theydisconnect the graph into two parts: the part below them (for concreteness,think of a child leaf), and the root component.
- Blowing up a leaf has no effect, since it does not connect two components, a leaf only connects itself to the main tree.
- The root of the tree is special; If it has only one child, then it acts likea leaf, since the root connects itself to the only component. On the otherhand, if there are multiple components, then the root acts like an internalnode, holding these different components together, making the root anarticulation vertex.
§ Articulation vertices on the DFS graph - undireced
- DFS of a general undirected graph also contains back edges. These act assecurity cables that link a vertex back to its ancestor. The securitycable from
x
to y
ensures that none of the nodes on the path [x..y]
can be articulation vertices.
- So, to find articulation vertices, we need to see how far back the security cables go.
int anc[V]; int dfs_outdeg[V];
void processs_vertex_early(int v) { anc[v] = v; }
void process_edge(int x, int y) {
if (dfsedge[x][y].type == TREE) { dfs_outdeg[x]++; }
if (dfsedge[x][y].type == BACK && (parent[y] != x)) {
if(entry_time[y] < entry_time[anc[x]]) {
anc[x] = y;
}
}
}
In a DFS tree, a vertex v (other than the root) is an articulation vertex iff v is not a leaf and some subtree of v has no back edge incident until a proper ancestor of v.
§ References