Basic numberings

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

Let [math]\displaystyle{ \,G }[/math] be a cf-graph with 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.

Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.