CONNECTIVITY (GRAPH THEORY)

In mathematics and computer science, 'connectivity' is one of the basic concepts of graph theory. It is closely related to the theory of network flow problems. The connectivity of a graph is an important measure of its robustness as a network.

Contents

Definitions of components, cuts and connectivity

Menger's theorem

Computational aspects

Examples

Properties

See also

Definitions of components, cuts and connectivity

In an undirected graph ''G'', two vertices ''u'' and ''v'' are called 'connected' if ''G'' contains a path from ''u'' to ''v''. Otherwise, they are called 'disconnected'. A graph is called 'connected' if every pair of distinct vertices in the graph is connected. A connected component is a maximal connected subgraph of ''G''. Each vertex belongs to exactly one connected component, as does each edge.
A directed graph is called 'weakly connected' if replacing all of its directed edges with undirected edges produces a connected (undirected) graph. It is 'strongly connected' or 'strong' if it contains a directed path from ''u'' to ''v'' for every pair of vertices ''u'',''v''.
The 'strong components' are the maximal strongly connected subgraphs
2-connectivity is also called "biconnectivity" and 3-connectivity is also called "triconnectivity".
A 'cut' or 'vertex cut' of a connected graph ''G'' is a set of vertices whose removal renders ''G'' disconnected. The 'connectivity' or vertex connectivity κ(''G'') is the size of a smallest vertex cut. A graph is called '''k''-connected' or '''k''-vertex-connected' if its vertex connectivity is ''k'' or greater. A complete graph with ''n'' vertices has no cuts at all, but by convention its connectivity is ''n''-1. A vertex cut for two vertices ''u'' and ''v'' is a set of vertices whose removal from the graph disconnects ''u'' and ''v''. The 'local connectivity' κ(''u'',''v'') is the size of a smallest vertex cut separating ''u'' and ''v''. Local connectivity is symmetric; that is, κ(''u'',''v'')=κ(''v'',''u''). Moreover, κ(''G'') equals the minimum of κ(''u'',''v'') over all pairs of vertices ''u'',''v''.
Analogous concepts can be defined for edges. Thus an 'edge cut' of ''G'' is a set of edges whose removal renders the graph disconnected,
the edge-connectivity κ′(''G'') is the size of a smallest edge cut, and the 'local edge-connectivity' κ′(''u'',''v'') of two vertices ''u'',''v'' is the size of a smallest edge cut disconnecting ''u'' from ''v''. Again, local edge-connectivity is symmetric.
A graph is called '''k''-edge-connected' if its edge connectivity is ''k'' or greater.
All of these definitions and notations carry over to directed graphs. Local connectivity and local edge-connectivity are not necessarily symmetric for directed graphs.

Menger's theorem

One of the most important facts about connectivity in graphs is Menger's theorem, which characterizes the connectivity and edge-connectivity of a graph in terms of the number of independent paths between vertices.
If ''u'' and ''v'' are vertices of a graph ''G'', then a collection of paths between ''u'' and ''v'' is called 'independent' if no two of them share a vertex (other than ''u'' and ''v'' themselves). Similarly, the collection is 'edge-independent' if no two paths in it share an edge. The greatest number of independent paths between ''u'' and ''v'' is written as λ(''u'',''v''), and the greatest number of edge-independent paths between ''u'' and ''v'' is written as λ′(''u'',''v'').
Menger's theorem asserts that κ(''u'',''v'') = λ(''u'',''v'') and κ′(''u'',''v'') = λ′(''u'',''v'') for every pair of vertices ''u'' and ''v''. This fact is actually a special case of the max-flow min-cut theorem.

Computational aspects

The problem of determining whether two vertices in a graph are connected can be solved efficiently using a search algorithm, such as breadth-first search. More generally, it is easy to determine computationally whether a graph is connected (for example, by using a disjoint-set data structure), or to count the number of connected components.
By Menger's theorem, for any two vertices ''u'' and ''v'' in a connected graph ''G'', the numbers κ(''u'',''v'') and κ′(''u'',''v'') can be determined efficiently using the max-flow min-cut algorithm. The connectivity and edge-connectivity of ''G'' can then be computed as the minimum values of κ(''u'',''v'') and κ′(''u'',''v''), respectively.
In computational complexity theory, SL is the class of problems log-space reducible to the problem of determining whether two vertices in a graph are connected, which was proved to be equal to L by Omer Reingold in 2004.
Hence, directed graph connectivity may be solved in $O(log\; n)$ space.

Examples

★ The vertex- and edge-connectivities of a disconnected graph are both 0.

★ 1-connectedness is synonymous with connectedness.

★ The complete graph on ''n'' vertices has edge-connectivity equal to ''n'' − 1. Every other simple graph on ''n'' vertices has strictly smaller edge-connectivity.

★ In a tree, the local edge-connectivity between every pair of vertices is 1.

Properties

★ Connectedness is preserved by graph homomorphisms.

★ If ''G'' is connected then its line graph ''L''(''G'') is also connected.

★ The vertex-connectivity of a graph is less than or equal to its edge-connectivity. That is, κ(G) ≤ κ′(G).

★ If a graph ''G'' is ''k''-connected, then for every set of vertices ''U'' of cardinality ''k'', there exists a cycle in ''G'' containing ''U''. The converse is true when ''k'' = 2.

★ A graph ''G'' is 2-edge-connected if and only if it has an orientation that is strongly connected.

See also

★ Algebraic connectivity