N-Нумерация

Материал из WikiGrapp
Перейти к:навигация, поиск

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

N-Numbering.png

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

Литература

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