Graph Theory Definitions

From DocR21

These definitions cover some basic terms and concepts of graph theory and how they have been implemented as C++ classes.

Definitions

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. Example of a Graph 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 the following figure 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. Example of a Graph shows a graph with three components, vertices A-L, and ten edges. Figure. Example of a Subgraph shows a subgraph and one of the three components of the graph depicted in the first figure.

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. Example of a Subgraph, 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. Example of a Graph 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.

Implementation

The concepts of vertex, edge, and graph have been implemented as the C++ classes gvertex, gedge, and generic_graph. (The entity_gvertex class is derived from the gvertex class. It contains an additional pointer to an ENTITY in the model. For example, an entity_gvertex could point to a cell or a face.)

Several graphs may refer to the same gedges and gvertices without having to copy their data. Instances of gvertex and gedge are use counted in the same way that laws are use counted. That is, they are copied by calling the add method and deleted by calling the remove method.

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.