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
The
nullity of
G, written μ(
G), is
Thus ρ(
G) + μ(
G) =
eWith 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 V1, V2,… 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 E1, E2,… be the sets of edges connecting vertices within V1, V2,… Then each of the graphs Gi with vertices Vi and edges Ei 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.