4.3.2. Format of an invariant
As we previously saw, we have graph invariants that hold for any digraph
as well as tighter graph invariants for specific graph classes.
As a consequence, we partition the database in groups of graph invariants.
A group of graph invariants corresponds to several invariants such that all invariants
relate the same subset of graph parameters and such that all invariants are variations of
the first invariant of the group taking into accounts the graph class.
Therefore, the first invariant of a group has no precondition, while all other invariants
have a non-empty precondition that characterises the graph class for which they hold.
EXAMPLE:
As a first example consider the group of invariants denoted by Proposition
68, which relate the number of arcs
with the number of vertices of the smallest and largest
connected component (i.e.,Β and ).
On the one hand, since the first rule has no precondition it corresponds to a general graph invariant.
On the other hand the second rule specifies a tighter condition (since is greater
than or equal to , which only holds for a final graph
that is reflexive, symmetric and transitive.
EXAMPLE:
As a second example, consider the following group of invariants corresponding to
PropositionΒ 51, which relate the number of arcs to
the number of vertices according to the arc generator
(see FigureΒ 2.3.4) used for generating the initial digraph: