connected graph

connected graph A graph in which there is a path joining each pair of vertices, the graph being undirected. It is always possible to travel in a connected graph between one vertex and any other; no vertex is isolated. If a graph is not connected it will consist of several components, each of which is connected; such a graph is said to be disconnected.

If a graph G has e edges, v vertices, and p components, the rank of G, written ρ(G), is defined to be v – p

The nullity of G, written μ(G), is e – v + p Thus ρ(G) + μ(G) = e

With reference to a directed graph, a weakly connected graph is one in which the direction of each edge must be removed before the graph can be connected in the manner described above. If however there is a directed path between each pair of vertices u and v and another directed path from v back to u, the directed graph is strongly connected.

More formally, let G be a directed graph with vertices V and edges E. The set V can be partitioned into equivalence classes V₁, V₂,… under the relation that vertices u and v are equivalent iff there is a path from u to v and another from v to u. Let E₁, E₂,… be the sets of edges connecting vertices within V₁, V₂,… Then each of the graphs G_i with vertices V_i and edges E_i is a strongly connected component of G. A strongly connected graph has precisely one strongly connected component.

The process of replacing each of the strongly connected components of a directed graph by a single vertex is known as condensation.