We want readers of this page not to misunderstand the reason for its existence: the aim is not to "rewrite" graph theory, but to use a mathematical model with terminology consistent with the nomenclature of the library entities.

Therefore, many of the terms you'll find in this library will have slightly different meanings than those you've probably already learned.

Mathematical definitions

The following definitions may at first glance seem overly complex compared to those you've probably already encountered in graph theory (especially that of a graph vertex), but we assure you that everything will become clear once you read the code documentation.

Warning: So, no need to worry: you don't need to fully understand the following definitions IMMEDIATELY, as they will be referenced later in the code documentation.

Graph

\( G \) is a graph if and only if \( G \) is an ordered 8-tuple that satisfies all of the following conditions:

\( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \) ;
\( V_\text{type} \) is a set;
\( V \subseteq V_\text{type} \times \mathbb{N} \) ; ( \( \mathbb{N} \) is the set containing only \( 0 \) and and all positive integers. See also the Cartesian product definition)
\( V \) is a finite set;
\( E_\text{di} \subseteq V \times V \) ;
\( E_\text{un} \subseteq \{ u \mid u \subseteq V \wedge ( | u | = 1 \vee | u | = 2 ) \} \) ; (If \( S \) is a finite set, then \( | S | \) denotes the number of elements of \( S \))
\( C_{l_V} \) is a set;
\( l_V \) is a function having as its codomain the set \( C_{l_V} \) and as its domain the set \( D_{l_V} \) such that \( D_{l_V} = \begin{cases} V & \text{if } C_{l_V} \neq \emptyset \\ \emptyset & \text{if } C_{l_V} = \emptyset \end{cases} \) ; (See the "empty function" definition)
\( C_{l_E} \) is a set;
\( l_E \) is a function having as its codomain the set \( C_{l_E} \) and as its domain the set \( D_{l_E} \) such that \( D_{l_E} = \begin{cases} E_\text{di} \cup E_\text{un} & \text{if } C_{l_E} \neq \emptyset \\ \emptyset & \text{if } C_{l_E} = \emptyset \end{cases} \) ;

Note: Let \( G \) be a graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \).
In mathematics, sets and functions should be considered static entities, so \( G \) does not "change over time".
Obviously, in programming, the definition of a graph must be modified to make graphs dynamic over time.
Therefore, in programming, sets \( V \), \( E_\text{di} \) and \( E_\text{un} \) and functions \( l_V \) and \( l_E \) are considered "dynamic over time", while retaining the properties listed above.

Example

Let \( A \) be the set of all lowercase English letters.
Let \( V \) such that \( V = \{ (a,0) , (b,0) , (c,0) , (d,0) , (e,0) , (f,0) , (g,0) \} \).
Let \( E_\text{di} = \{ ( (a,0) , (b,0) ) , ( (c,0) , (a,0) ) , ( (a,0) , (d,0) ) , ( (d,0) , (a,0) ) , ( (d,0) , (d,0) ) , ( (e,0) , (e,0) ), ( (a,0) , (f,0) ) \} \).
Let \( E_\text{un} = \{ \{ (c,0) \}, \{ (a,0) , (e,0) \} , \{ (e,0) \} , \{ (a,0) , (f,0) \} \} \).
Let \( f \) such that \( f : \emptyset \to \emptyset \).
Let \( G \) such that \( G = ( A , V , E_\text{di} , E_\text{un} , \emptyset , f , \emptyset , f ) \).
\( G \) is a graph.
The following is a graphical visualization of \( G \).

dot_inline_dotgraph_cf7dc2cc0aedc613ef83b7ec8a4fa712.png

Vertex of a graph

Let \( G \) be a graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \).
\( v \) is a vertex of \( G \) if and only if \( v \in V \).

Core of a vertex of a graph

Let \( G \) be a graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \).
For each vertex \( v \) of \( G \) such that \( v = ( x , n ) \), \( x \) is the core of \( v \).

Multiplicity of a vertex of a graph

Let \( G \) be a graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \).
For each vertex \( v \) of \( G \) such that \( v = ( x , n ) \), the multiplicity of \( v \) with respect to \( G \) is the number of vertices of \( G \) that have \( x \) as their cores , including \( v \) in the count.
( i.e., more formally, \( | \{ w | w \in V \wedge \exists m | w = ( x , m ) \} | \) ).

Edge of a graph

Let \( G \) be a graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \).
\( y \) is an edge of \( G \) if and only if \( y \in E_\text{di} \cup E_\text{un} \).

Directed edge of a graph

Let \( G \) be a graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \).
\( d \) is a directed edge of \( G \) if and only if \( d \in E_\text{di} \).

Undirected edge of a graph

Let \( G \) be a graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \).
\( u \) is an undirected edge of \( G \) if and only if \( u \in E_\text{un} \).

Tail of a directed edge of a graph

Let \( G \) be a graph.
Let \( d \) be a directed edge of \( G \).
\( t \) is the tail of \( d \) if and only if \( d = ( t , h )\).

Head of a directed edge of a graph

Let \( G \) be a graph.
Let \( d \) be a directed edge of \( G \).
\( h \) is the head of \( d \) if and only if \( d = ( t , h )\).

Endpoint of an edge of a graph

Let \( G \) be a graph.
Let \( y \) be an edge of \( G \).
\( a \) is an endpoint of \( y \) if and only if \( y \) satisfies one of the following conditions:

\( y \) is a directed edge (of \( G \) ) with \( y = ( a , b ) \);
\( y \) is a directed edge (of \( G \) ) with \( y = ( b , a ) \);
\( y \) is an undirected edge (of \( G \) ) and \( a \in y \);

Out-edge of a vertex of a graph

Let \( G \) be a graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \) .
Let \( v \) be a vertex of \( G \).
\( y \) is an out-edge of \( v \) with respect to \( G \) if and only if \( y \) satisfies one of the following conditions:

\( y \) is a directed edge of \( G \) and \( v \) is the head of \( y \);
\( y \) is a undirected edge of \( G \) and \( v \) is an endpoint of \( y \);

Undirected out-edge of a vertex of a graph

Let \( G \) be a graph.
Let \( v \) be a vertex of \( G \).
\( y \) is an undirected out-edge of \( v \) with respect to \( G \) if and only if \( y \) satisfies all the following conditions:

\( y \) is an undirected edge of \( G \);
\( y \) is an out-edge of \( v \) with respect to \( G \);

Directed out-edge of a vertex of a graph

Let \( G \) be a graph.
Let \( v \) be a vertex of \( G \).
\( y \) is a directed out-edge of \( v \) with respect to \( G \) if and only if \( y \) satisfies all the following conditions:

\( y \) is an directed edge of \( G \);
\( y \) is an out-edge of \( v \) with respect to \( G \);

Set graph

\( G \) is a set graph if and only if \( G \) is a graph and the multiplicity of any vertex of \( G \) (with respect to \( G \)) is equal to \( 1 \).

Multiset graph

\( G \) is a multiset graph if and only if \( G \) is a graph and exists (at least one) \( v \) such that \( v \) is a vertex of G and the multiplicity of \( v \) (with respect to \( G \)) is strictly greater than \( 1 \) .

Mixed graph

\( G \) is a mixed graph if and only if \( G \) satisfies all the following conditions:

\( G \) is a graph;
exists (at least) a directed edge of \( G \);
exists (at least) an undirected edge of \( G \);

Non-mixed graph

\( G \) is a non-mixed graph if and only if \( G \) satisfies all the following conditions:

\( G \) is a graph;
\( G \) is not a mixed graph;

Digraph

\( G \) is a digraph if and only if \( G \) is a graph and there is no undirected edge of \( G \).

Ugraph

\( G \) is a ugraph if and only if \( G \) is a graph and there is no directed edge of \( G \).

Labeled-edge graph

\( G \) is a labeled-edge graph if and only if \( G \) satisfies all the following conditions:

\( G \) is a graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \);
\( C_{l_E} \neq \emptyset \);

Edge label of a labeled-edge graph

Let \( G \) be a labeled-edge graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \) ( \( C_{l_E} \neq \emptyset \) ).
If \( y \) is an edge of \( G \), then \( l_E(y) \) is the label of \( y \) with respect to \( G \).

Labeled-vertex graph

\( G \) is a labeled-vertex graph if and only if \( G \) satisfies all the following conditions:

\( G \) is a graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \);
\( C_{l_V} \neq \emptyset \);

Vertex label of a labeled-vertex graph

Let \( G \) be a labeled-vertex graph with \( G = ( V_\text{type} , V , E_\text{di} , E_\text{un} , C_{l_V} , l_V , C_{l_E} , l_E ) \) ( \( C_{l_V} \neq \emptyset \) ).
If \( v \) is a vertex of \( G \), then \( l_V(v) \) is the label of \( v \) with respect to \( G \).

Full labeled graph

\( G \) is a full labeled graph if and only if \( G \) satisfies all the following conditions:

\( G \) is a labeled-edge graph;
\( G \) is a labeled-vertex graph;

Unlabeled graph

\( G \) is a unlabeled graph if and only if \( G \) satisfies all the following conditions:

\( G \) is not a labeled-edge graph;
\( G \) is not a labeled-vertex graph;