# Basic numberings

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

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);

(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) 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) if and only if either $\,p$ is $\,M$-reachable from $\,q$ or $\,M(p) 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);

(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) and $\,N(q);

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

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)$

## Литература

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