Graph connectivity

1 Basic definitions

Let [math]G = (V, E)[/math] be a given (directed or undirected) graph. The sequence [math]P(u, v)[/math] of edges [math]e_1 = (u, w_1)[/math], [math]e_2 = (w_1, w_2)[/math], …, [math]e_k = (w_{k-1}, v)[/math] is called a "path from the vertex [math]u[/math] to [math]v[/math]. In this case, the vertex [math]v[/math] is reachable from [math]u[/math]. It is assumed that the empty path [math]P(u, u)[/math] leads from [math]u[/math] to itself; that is, each vertex is reachable from itself. A nonempty path [math]P(u, u)[/math] is called a cycle (or a closed walk).

Undirected graph is said to be connected if all its vertices are reachable from a certain vertex (or, equivalently, from any vertex of this graph).

Directed graph is said to be

• weakly connected if the corresponding undirected graph is connected;
• strongly connected if every vertex [math]v[/math] is reachable from any other vertex [math]v[/math].

A connected component of an undirected graph is a maximum (with respect to inclusion) connected subgraph of this graph.

A strongly connected component of a directed graph is a maximum (with respect to inclusion) strongly connected subgraph. In other words, any two vertices of this subgraph belong to a cycle, and it contains all such cycles for its vertices.

A bridge in a graph is an edge whose removal increases the number of connected components.

A joint in a graph is a vertex whose removal increases the number of connected components.

A connected graph is said to be "[math]k[/math]-vertex-connected (or simply [math]k[/math]-connected) if it has more than [math]k[/math] vertices and remains connected after removal any [math]k-1[/math] of its vertices. The maximum such number [math]k[/math] is called the vertex connectivity (or simply connectivity) of this graph. A 1-connected graph is said to be connected, while a 2-connected graph is said to be biconnected.

A connected graph is said to be "[math]k[/math]-edge-connected if it remains connected after removal any [math]k-1[/math] of its edges. The maximum such number [math]k[/math] is called the "edge connectivity of this graph.

A biconnected component of a graph is a maximum (with respect to inclusion) biconnected subgraph of this graph.

2 Properties

A connected component can equivalently be defined via its set of vertices. These are:

• all the vertices reachable from some vertex;
• a set of vertices that are reachable from each other and are not reachable from other vertices.

The relation "a vertex [math]v[/math] is reachable from a vertex [math]u[/math]" is an equivalence relation. Thus, the search for the connected components of a graph is the same as the reconstruction of a complete equivalence relation from its part.

Alternative definitions of a bridge are as follows:

• an edge is a bridge if it belongs to no cycle;
• an edge [math]e[/math] is a bridge if there exists a pair of vertices [math](u, v)[/math] of the same connected component such that any path [math]P(u, v)[/math] between these vertices goes through this edge [math]e[/math].

A joint separates biconnected components (if two biconnected components have a common vertex, then this vertex is a joint).

Every vertex of a bridge is a joint (excepting the case where the bridge is the only edge incident to this vertex).

A strongly connected component is the union of all the cycles that pass through its vertices.

3 Algorithms

Connected components can be found by the following algorithms:

• a systematic application of the breadth first search. The time complexity is [math]O(m)[/math];
• the use of a system of disjoint sets The time complexity is [math]O(m \alpha(m, n))[/math]. An effective multithreaded implementation is possible ;
• the parallel algorithm of Shiloach-Vishkin The time complexity is [math]O(\ln n)[/math], provided that [math]n + 2m[/math] processors are used.

Strongly connected components can be found by the following algorithms:

• Tarjan's algorithm (in course of depth first search). The time complexity is [math]O(m)[/math];
• the parallel DCSC algorithm The complexity is [math]O(n \ln n)[/math].

Bridges can be found by the following algorithms:

• Tarjan's bridge-finding algorithm (in course of depth first search). The time complexity is [math]O(m)[/math];
• the parallel Tarjan-Vishkin algorithm The time complexity is [math]O(\ln n)[/math], provided that [math]O(m + n)[/math] processors are used;
• the online Westbrook-Tarjan algorithm The time complexity is [math]O(m \alpha(m, n))[/math].

Biconnected components can be found by the following algorithms:

• Tarjan's algorithm (in course of depth first search). The time complexity is [math]O(m)[/math] (the algorithm also finds the corresponding joints);
• the parallel Tarjan-Vishkin algorithm The time complexity is [math]O(\ln n)[/math], provided that [math]O(m + n)[/math] processors are used (the algorithm is also able to find bridges);
• the online Westbrook-Tarjan algorithm . The time complexity is [math]O(m \alpha(m, n))[/math].

The problem of finding the vertex connectivity of a graph reduces to the search for maximal flows and can be solved in time [math]O(\min\{k^3 + n, kn\} m)[/math].

The edge connectivity of a graph can be found by using Gabow's algorithm The time complexity is [math]O(k m \ln (n^2/m))[/math] for directed graphs and [math]O(m + k^2 n \ln (n/k))[/math] for undirected ones. The same algorithm is able to check the [math]k[/math]-connectivity in time [math]O(m + n \ln n)[/math].