|
These definitions cover some basic terms and concepts of graph theory and how they have been implemented as
C++ classes.
|
|
|
A
relation is a set of ordered pairs. If all of the elements of the ordered pairs come from a set S, then the relation may be said to be on the set S. A relation
R is called
symmetric if for each ordered pair (a,b) in
R, the ordered pair (b,a) is also in
R.
|
|
|
A
graph is a symmetric relation on a set
V representing the vertices of
S. The ordered pairs of a graph are called
edges of the graph. No distinction is made between the pair (a,b) and the pair (b,a). The vertices
a and
b are said to be
adjacent to the edge (a,b). The edge (a,b) is said to be
adjacent to the vertices
a and
b.
|
|
|
A
path is a distinct sequence of vertices v0, v1, v2,..., vn such that for all
i<n, vi is adjacent to vi+1. The vertex v0 is the start of the path. The vertex vn is the end of the path. The integer
n is the length of the path. Sometimes the graph defined by the sequence of vertices together with the edges that connect them is also called a
path. An example of a path in Figure 5-1 would be the sequence of vertices (B, A, E, D, F).
|
|
|
A graph
G is called
connected if given any two vertices
a and
b in
G, there is a path in
G from
a to
b. The graph in Figure 5-1 is not connected, because there is no path from the vertex A to the vertex K.
|
|
|
A graph
S is called a
subgraph of
G if every vertex and edge in
S is also in
G. A maximum connected subgraph of
G is called a
component of G.
|
|
|
Figure 5-1 shows a graph with three components, vertices A-L, and ten edges. Figure 5-2 shows a subgraph and one of the three components of the graph depicted in Figure 5-1.
|
|
|
|
|
Figure 5-1. Example of a Graph
|
|
|
|
|
Figure 5-2. Example of a Subgraph
|
|
|
A
cycle is a sequence of at vertices v0, v1, v2,..., vn such that v0= vn and v0, v1, v2,..., vn-1 is a path. A graph is called a
cycle if it is connected and non-empty and if every vertex is of degree two. A vertex
v is called a
cycle vertex of the graph
G if
v belongs to a cycle in the graph
G. The
degree of a vertex is the number of adjacent edges to the vertex. The
distance between two vertices in a graph is the length of the shortest path in the graph from one vertex to the other.
|
|
|
In Figure 5-2, the sequence of vertices (A, B, C, D, E, A) is a cycle, with each being a cycle vertex. The vertices
G and
F are not cycle vertices. The degree of vertices
D,
E, and
J from Figure 5-1 is three. The degree of vertices
A, B, and
C is two, while the degree of vertices
G, F, I, K, and
L is one and the degree of vertex
H is zero.
|
|
|
A graph is called a
tree if it is connected and does not contain a cycle. A graph is called
linear if it is a tree and if it does not contain a vertex of degree greater than two.
|
|
|
The concepts of vertex, edge, and graph have been implemented as the
C++ classes
gvertex,
gedge, and
generic_graph. (entity_gvertex is derived from
gvertex except that it contains a pointer to an entity in the model. Such an entity could be a cell or a face.) A
gvertex may be created with an optional
char *name. A
gedge may be created with two
gvertex pointers. An empty graph may be created and edges and vertices may be added to it by calling its
add_vertex and
add_edge methods. Once created, a graph may be interrogated, ordered, or subsetted in a number of ways.
|
|
|
The
generic_graph class has methods to tell if a graph is:
|
|
|
connected
|
|
|
a tree
|
|
|
linear
|
|
|
a cycle
|
|
|
It also has methods to tell how many components the graph has and to return each of the components as a subgraph. The components may also be identified by giving an edge or vertex in them.
|