Numbering of cf-graph

Numbering of cf-graph --- нумерация уграфа.

Let [math]\displaystyle{ G }[/math] be a cf-graph with a set of nodes [math]\displaystyle{ X }[/math], where [math]\displaystyle{ n=|X| }[/math]. A bijection [math]\displaystyle{ F: \; X \rightarrow [1,n] }[/math] is called a numbering of [math]\displaystyle{ G }[/math]. [math]\displaystyle{ F(p) }[/math] is called [math]\displaystyle{ F }[/math]-number of the node [math]\displaystyle{ p }[/math], and [math]\displaystyle{ F^{-1}(k) }[/math] denotes the node [math]\displaystyle{ p }[/math] having [math]\displaystyle{ F }[/math]-number [math]\displaystyle{ k }[/math]. By [math]\displaystyle{ F[i,j] }[/math] we denote a set of nodes [math]\displaystyle{ \{p\in X: F(p)\in [i,j]\} }[/math] and the subgraph of [math]\displaystyle{ G }[/math] induced by the set.

An arc [math]\displaystyle{ u=(p,q) }[/math] is called an [math]\displaystyle{ F }[/math]direct arc (or [math]\displaystyle{ F }[/math]arc) if [math]\displaystyle{ F(p)\lt F(q) }[/math] and an [math]\displaystyle{ F }[/math]inverse arc if [math]\displaystyle{ F(p)\geq F(q) }[/math].

The depth (or the number of noncongruence) of the numbering [math]\displaystyle{ F }[/math] of the graph [math]\displaystyle{ G }[/math] is defined as the greatest number of [math]\displaystyle{ F }[/math]-inverse arcs that belongs to a simple path in [math]\displaystyle{ G }[/math].

If a path [math]\displaystyle{ P }[/math] from a node [math]\displaystyle{ p }[/math] to a node [math]\displaystyle{ q }[/math] does not contain any [math]\displaystyle{ F }[/math]-inverse arcs, then it is called an [math]\displaystyle{ F }[/math]path and the node [math]\displaystyle{ q }[/math] is called [math]\displaystyle{ F }[/math]reachable from [math]\displaystyle{ p }[/math].

Let [math]\displaystyle{ p }[/math] be a node of [math]\displaystyle{ G }[/math] with [math]\displaystyle{ F }[/math]-number [math]\displaystyle{ i }[/math], i.e. [math]\displaystyle{ F(p)=i }[/math]. A subgraph of [math]\displaystyle{ G }[/math] that consists of all those nodes from which [math]\displaystyle{ p }[/math] is reachable in [math]\displaystyle{ F[i,n] }[/math] is called [math]\displaystyle{ F }[/math]region and denoted by [math]\displaystyle{ F\lt p\gt }[/math] or [math]\displaystyle{ F\lt i\gt }[/math].