0.7 Graphs  (Page 19/21)

Connected component labeling in image analysis

In image analysis, some of the most efficient connected component labeling algorithms make use of union-find data structure. In this type of application, the time required form union-find operations is strictly linear.

7.5. connectivity

(From Wikipedia, the free encyclopedia)

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.

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).