N-Нумерация

Материал из WEGA
Версия от 17:19, 24 ноября 2009; Glk (обсуждение | вклад) (Создана новая страница размером '''N-Нумерация''' (''N-Numbering'') - для данной <math>M</math>-''нумерации'' такая нумерация <...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

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

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

Литература

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

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