N-Нумерация

Материал из WEGA

N-Нумерация (N-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]-нумерацией образуют пару базисных нумераций.

N-Numbering.png

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

Литература

[Касьянов/88],

[Евстигнеев-Касьянов/94]