Basic numberings

Basic numberings --- базисные нумерации.

Let [math]\displaystyle{ G }[/math] be a cf-graphwith the initial node[math]\displaystyle{ p_0 }[/math]. Basic numberings [math]\displaystyle{ M }[/math] and [math]\displaystyle{ N }[/math] of [math]\displaystyle{ G }[/math] are defined as follows.

A numbering [math]\displaystyle{ F }[/math] of a cf-graph [math]\displaystyle{ G }[/math] is called a direct numbering (or an [math]\displaystyle{ M }[/math]-numbering) of [math]\displaystyle{ G }[/math] if the following three properties hold:

(1) [math]\displaystyle{ F(p_0)=1 }[/math];

(2) for any node [math]\displaystyle{ p }[/math] distinct from [math]\displaystyle{ p_0 }[/math] there is a predecessor [math]\displaystyle{ q }[/math] of [math]\displaystyle{ p }[/math] such that [math]\displaystyle{ F(q)\lt F(p) }[/math];

(3) for any two nodes [math]\displaystyle{ q }[/math] and [math]\displaystyle{ p }[/math], if [math]\displaystyle{ (q,p) }[/math] is an [math]\displaystyle{ F }[/math]-direct arc and [math]\displaystyle{ F[F(q)+1,F(p)-1] }[/math] contains no predecessors of [math]\displaystyle{ p }[/math], then [math]\displaystyle{ F(r)\lt F(p) }[/math] for any successor [math]\displaystyle{ r }[/math] of any node from [math]\displaystyle{ F[F(q)+1,F(p)-1] }[/math].

A numbering [math]\displaystyle{ F }[/math] of [math]\displaystyle{ G }[/math] is called an inverse numbering (or an [math]\displaystyle{ N }[/math]-numbering) correlated with a direct numbering [math]\displaystyle{ M }[/math] of [math]\displaystyle{ G }[/math] if for any two nodes [math]\displaystyle{ q }[/math] and [math]\displaystyle{ p }[/math] of [math]\displaystyle{ G }[/math], [math]\displaystyle{ F(q)\lt F(p) }[/math] if and only if either [math]\displaystyle{ p }[/math] is [math]\displaystyle{ M }[/math]-reachable from [math]\displaystyle{ q }[/math] or [math]\displaystyle{ M(p)\lt M(q) }[/math] and [math]\displaystyle{ q }[/math] is not [math]\displaystyle{ M }[/math]-reachable from [math]\displaystyle{ p }[/math].

Any cf-graph [math]\displaystyle{ G }[/math] has at least one pair of correlated basic numberings, but the same inverse numbering of [math]\displaystyle{ G }[/math] can be correlated with different direct numberings of [math]\displaystyle{ G }[/math].

The set of all arcs [math]\displaystyle{ (p,q) }[/math] of [math]\displaystyle{ G }[/math] is divided with respect to its correlated basic numberings [math]\displaystyle{ M }[/math] and [math]\displaystyle{ N }[/math] into the four subclasses: tree arcs [math]\displaystyle{ T }[/math], forward arcs [math]\displaystyle{ F }[/math], backward arcs [math]\displaystyle{ B }[/math] and cross arcs [math]\displaystyle{ C }[/math] defined as follows:

(1) [math]\displaystyle{ (p,q)\in T }[/math] iff [math]\displaystyle{ (p,q) }[/math] is [math]\displaystyle{ M }[/math]-direct arc and there is no [math]\displaystyle{ M }[/math]-direct arc [math]\displaystyle{ (s,q) }[/math] such that [math]\displaystyle{ M(p)\lt M(s) }[/math];

(2) [math]\displaystyle{ (p,q)\in F }[/math] iff [math]\displaystyle{ (p,q) }[/math] is [math]\displaystyle{ M }[/math]-direct arc and [math]\displaystyle{ (p,q)\not \in T }[/math];

(3) [math]\displaystyle{ (p,q)\in B }[/math] iff [math]\displaystyle{ M(q)\lt M(p) }[/math] and [math]\displaystyle{ N(q)\lt N(p) }[/math];

(4) [math]\displaystyle{ (p,q)\in C }[/math] iff [math]\displaystyle{ M(q)\lt M(p) }[/math] and [math]\displaystyle{ N(p)\lt N(q) }[/math].

A graph [math]\displaystyle{ (X, T, p_0) }[/math] were [math]\displaystyle{ X }[/math] is the set of vertices of [math]\displaystyle{ G }[/math] is a spanning tree of [math]\displaystyle{ G }[/math] with root [math]\displaystyle{ p_0 }[/math].

Every pair of correlated basic numberings can be computed in linear time by the procedure [math]\displaystyle{ DFS(p_0) }[/math]

See

• Depth-first search.