Basic numberings: различия между версиями

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

Let <math>G</math> be a ''cf-graph''with the ''initial node''<math>p_0</math>.

'''Basic numberings''' <math>M</math> and <math>N</math> of <math>G</math> are defined as follows.

A ''numbering'' <math>F</math> of a ''cf-graph'' <math>G</math> is called a '''direct''' numbering (or an <math>M</math>-'''numbering''') of <math>G</math> if the following

(1) <math>F(p_0)=1</math>;

(2) for any node <math>p</math> distinct from <math>p_0</math> there is

a predecessor <math>q</math> of <math>p</math> such that <math>F(q)<F(p)</math>;

(3) for any two nodes <math>q</math> and <math>p</math>, if

<math>(q,p)</math> is an ''<math>F</math>-direct arc'' and <math>F[F(q)+1,F(p)-1]</math> contains no predecessors of <math>p</math>,

then <math>F(r)<F(p)</math> for any successor <math>r</math> of any node from <math>F[F(q)+1,F(p)-1]</math>.

A numbering <math>F</math> of <math>G</math> is called an '''inverse''' numbering (or an <math>N</math>-'''numbering''') '''correlated''' with

a direct numbering <math>M</math> of <math>G</math> if for any two nodes <math>q</math> and <math>p</math> of <math>G</math>,

<math>F(q)<F(p)</math> if and only if either <math>p</math> is ''<math>M</math>-reachable'' from <math>q</math> or

<math>M(p)<M(q)</math> and <math>q</math> is not <math>M</math>-reachable from <math>p</math>.

Any cf-graph <math>G</math> has at least one pair of correlated basic numberings, but the same

inverse numbering of <math>G</math> can be correlated with different direct numberings of <math>G</math>.

The set of all arcs <math>(p,q)</math> of <math>G</math> is divided

with respect to its correlated basic numberings <math>M</math> and <math>N</math>

into the four subclasses: '''tree arcs''' <math>T</math>, '''forward arcs''' <math>F</math>, '''backward arcs''' <math>B</math> and '''cross arcs''' <math>C</math> defined as follows:

(1) <math>(p,q)\in T</math> iff <math>(p,q)</math> is <math>M</math>-direct arc and there is no <math>M</math>-direct arc <math>(s,q)</math>

such that <math>M(p)<M(s)</math>;

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

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

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

A graph <math>(X, T, p_0)</math> were <math>X</math> is the set of vertices of <math>G</math> is a ''spanning tree'' of <math>G</math> with root <math>p_0</math>.

by the procedure <math>DFS(p_0)</math>  

*''Depth-first search''.