N-Нумерация

[math]\displaystyle{ \,N }[/math]-Нумерация ([math]\displaystyle{ \,N }[/math]-Numbering) — для данной [math]\displaystyle{ \,M }[/math]-нумерации такая нумерация [math]\displaystyle{ \,N }[/math] вершин, что для любых вершин [math]\displaystyle{ \,a }[/math] и [math]\displaystyle{ \,b }[/math] неравенство [math]\displaystyle{ \,N(a) \lt N(b) }[/math] выполняется тогда и только тогда, когда либо вершина [math]\displaystyle{ \,b }[/math] [math]\displaystyle{ \,M }[/math]-достижима из [math]\displaystyle{ \,a, }[/math] либо [math]\displaystyle{ \,M(b) \lt M(a) }[/math] и вершина [math]\displaystyle{ \,a }[/math] не является [math]\displaystyle{ \,M }[/math]-достижимой из [math]\displaystyle{ \,b. }[/math] Вместе с [math]\displaystyle{ \,M }[/math]-нумерацией образуют пару базисных нумераций.

Другое название — Обратная нумерация.

Литература

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

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