Basic numberings — базисные нумерации.
A numbering of a cf-graph is called a direct numbering (or an -numbering) of if the following three properties hold:
(2) for any node distinct from there is a predecessor of such that ;
(3) for any two nodes and , if is an -direct arc and contains no predecessors of , then for any successor of any node from .
A numbering of is called an inverse numbering (or an -numbering) correlated with a direct numbering of if for any two nodes and of , if and only if either is -reachable from or and is not -reachable from .
Any cf-graph has at least one pair of correlated basic numberings, but the same inverse numbering of can be correlated with different direct numberings of .
The set of all arcs of is divided with respect to its correlated basic numberings and into the four subclasses: tree arcs , forward arcs , backward arcs and cross arcs defined as follows:
(1) iff is -direct arc and there is no -direct arc such that ;
(2) iff is -direct arc and ;
(3) iff and ;
(4) iff and .
Every pair of correlated basic numberings can be computed in linear time by the procedure
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.