L-Нумерация

[math]\displaystyle{ \,L }[/math]-Нумерация ([math]\displaystyle{ \,L }[/math]-Numbering) — нумерация вершин уграфа [math]\displaystyle{ \,G }[/math], которая определяется как последний член [math]\displaystyle{ \,L_{0} }[/math] последовательности нумераций [math]\displaystyle{ L_{n}, \; L_{n-1}, \; \ldots, \; L_{0} }[/math] в которой [math]\displaystyle{ \,L_{n} }[/math] есть [math]\displaystyle{ \,K }[/math]-нумерация и для любых вершин [math]\displaystyle{ p, \; q }[/math] и номера [math]\displaystyle{ \,i }[/math] справедливы следующие два свойства: если [math]\displaystyle{ \,L_{i}(p) \lt i }[/math] или [math]\displaystyle{ L_{i}(p) \gt i + |L_{i}\langle i\rangle| }[/math], то [math]\displaystyle{ \,L_{i-1}(p) = L_{i}(p) }[/math]; если [math]\displaystyle{ L_{i}(p), \; L_{i}(q) \in [i, i+|L_{i}\langle i\rangle |) }[/math], то [math]\displaystyle{ \,L_{i-1}(p) \lt L_{i-1}(q) }[/math] тогда и только тогда, когда либо [math]\displaystyle{ \,p }[/math] и [math]\displaystyle{ \,q }[/math] имеют один и тот же [math]\displaystyle{ \,L_{i} }[/math]-ранг в [math]\displaystyle{ [i,i + |L_{i}\langle i\rangle |) }[/math] и [math]\displaystyle{ \,L_{i}(p) \lt L_{i}(q) }[/math], либо [math]\displaystyle{ \,L_{i} }[/math]-ранг вершины [math]\displaystyle{ \,q }[/math] превышает [math]\displaystyle{ \,L_{i} }[/math]-ранг вершины [math]\displaystyle{ \,p }[/math] в [math]\displaystyle{ [i,i+|L_{i}\langle i\rangle |) }[/math].

Относительно обозначений см. [math]\displaystyle{ \,F }[/math]-Область и [math]\displaystyle{ F\, }[/math]-Ранг.

Литература

• Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.

• Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.