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

Перейти к навигации Перейти к поиску
нет описания правки
(Новая страница: «'''Basic numberings''' --- базисные нумерации. Let <math>G</math> be a ''cf-graph''with the ''initial node''<math>p_0</math>. '''Basic numberings''…»)
 
Нет описания правки
Строка 1: Строка 1:
'''Basic numberings''' --- базисные нумерации.
'''Basic numberings''' — ''[[базисные нумерации]].''


Let <math>G</math> be a ''cf-graph''with the ''initial node''<math>p_0</math>.
Let <math>\,G</math> be a ''[[Cf-Graph|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.
'''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
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
three properties hold:
three properties hold:


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


(2) for any node <math>p</math> distinct from <math>p_0</math> there is
(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>;
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
(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>,
<math>\,(q,p)</math> is an ''[[F-Direct arc|<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>.
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 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>,
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>\,F(q)<F(p)</math> if and only if either <math>\,p</math> is ''[[F-Reachable (from p) node|<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>.
<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
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>.
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
The set of all [[arc|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>
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:
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>
(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>;
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>;
(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>;
(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>.
(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>.
A [[graph, undirected graph, nonoriented graph|graph]] <math>\,(X, T, p_0)</math> were <math>\,X</math> is the set of [[vertex|vertices]] of <math>\,G</math> is a ''[[spanning tree]]'' of <math>\,G</math> with [[root]] <math>\,p_0</math>.


Every pair of correlated basic numberings can be computed in linear time
Every pair of correlated basic numberings can be computed in linear time
by the procedure <math>DFS(p_0)</math>  
by the procedure <math>\,DFS(p_0)</math>
==See==
==See==
*''Depth-first search''.
* ''[[Depth-first search (DFS)|Depth-first search]]''.
 
==Литература==
 
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.

Навигация