T-Numbering

[math]\displaystyle{ T }[/math]-Numbering --- [math]\displaystyle{ T }[/math]-нумерация.

Given a cf-graph [math]\displaystyle{ G }[/math] and its inverse numbering [math]\displaystyle{ N }[/math], a node [math]\displaystyle{ P }[/math] is called a binode (or [math]\displaystyle{ N }[/math]node) if [math]\displaystyle{ p\not \in N\lt i\gt }[/math] for all [math]\displaystyle{ i\lt N(p) }[/math].

A [math]\displaystyle{ T }[/math]numbering is such a numbering of [math]\displaystyle{ G }[/math] that the following two properties hold:

(1) [math]\displaystyle{ N\lt p\gt =T[T(p), T\lt p\gt +|N\lt p\gt |-1] }[/math] for any [math]\displaystyle{ N }[/math]-node [math]\displaystyle{ p }[/math],

(2) for any two [math]\displaystyle{ N }[/math]-nodes [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math], [math]\displaystyle{ T(p)\lt T(q) }[/math] if and only if [math]\displaystyle{ T(p)\lt T(q) }[/math].

A fragment [math]\displaystyle{ S }[/math] of [math]\displaystyle{ G }[/math] is its strongly connected component if and only if [math]\displaystyle{ S=N\lt p\gt }[/math] for an [math]\displaystyle{ N }[/math]-node [math]\displaystyle{ p }[/math].

An [math]\displaystyle{ N }[/math]-node [math]\displaystyle{ r }[/math] is called the cutpoint of [math]\displaystyle{ G }[/math] if there is no arc [math]\displaystyle{ (p,q) }[/math] such that [math]\displaystyle{ T(p)\lt T(r)\lt T(q) }[/math].

A fragment [math]\displaystyle{ H }[/math] of [math]\displaystyle{ G }[/math] is its linear component with the initial node [math]\displaystyle{ p }[/math] and the terminal node [math]\displaystyle{ q }[/math] if and only if, for some [math]\displaystyle{ T }[/math]-numbering of [math]\displaystyle{ G }[/math], the nodes [math]\displaystyle{ p }[/math] and [math]\displaystyle{ q }[/math] are cutnodes, [math]\displaystyle{ H=T[T(p), T(q)-1] }[/math], and [math]\displaystyle{ T[T(p)+1, T(q)-1] }[/math] contains no cutnodes.