L-Нумерация

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

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

Относительно обозначений см. \,F-Область и F\,-Ранг.

Литература

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