Connected Graph Definition/Meaning:
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 p(G), is defined to be
v - p
The nullity of G, written u(G),
is
e - v + p
Thus
p(G) + u(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 he 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 G1, with vertices V1,
and edges E1, 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.
|
