Basic numberings

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Let \,G be a cf-graph with the initial node \,p_0. Basic numberings \,M and \,N of \,G are defined as follows.

A numbering \,F of a cf-graph \,G is called a direct numbering (or an \,M-numbering) of \,G if the following three properties hold:

(1) \,F(p_0)=1;

(2) for any node \,p distinct from \,p_0 there is a predecessor \,q of \,p such that \,F(q)<F(p);

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

A numbering \,F of \,G is called an inverse numbering (or an N-numbering) correlated with a direct numbering \,M of \,G if for any two nodes \,q and \,p of \,G, \,F(q)<F(p) if and only if either \,p is \,M-reachable from \,q or \,M(p)<M(q) and \,q is not \,M-reachable from \,p.

Any cf-graph \,G has at least one pair of correlated basic numberings, but the same inverse numbering of \,G can be correlated with different direct numberings of \,G.

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

(1) (p,q)\in T iff \,(p,q) is \,M-direct arc and there is no \,M-direct arc \,(s,q) such that \,M(p)<M(s);

(2) (p,q)\in F iff \,(p,q) is \,M-direct arc and (p,q)\not \in T;

(3) (p,q)\in B iff \,M(q)<M(p) and \,N(q)<N(p);

(4) (p,q)\in C iff \,M(q)<M(p) and \,N(p)<N(q).

A graph \,(X, T, p_0) were \,X is the set of vertices of \,G is a spanning tree of \,G with root \,p_0.

Every pair of correlated basic numberings can be computed in linear time by the procedure \,DFS(p_0)

See

Литература

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