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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Новая страница: «'''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.

Текущая версия от 16:31, 23 октября 2018

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

Литература

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