K-Нумерация

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

\,K-Нумерация (\,K-Numbering) — нумерация вершин уграфа \,G, которая определяется как последний член \,K_{[n]} (\,n — число вершин в \,G) последовательности нумераций K_{1}, \; K_{2}, \; \ldots, \; K_{n}, в которой \,K_{1}обратная нумерация \,G и для любых i \in [1,n) и вершин \,p, q справедливы два свойства: если K_{i}(p) \in [1,i), то \,K_{i+1}(p) = K_{i}(p); если \,K_{i}(p), \; K_{i}(q) \in
[i,n], то \,K_{i+1}(p) < K_{i+1}(q) тогда и только тогда, когда либо p \in K_{i}\langle i\rangle и q \not \in K_{i}\langle i\rangle, либо \,K_{i}(p) <
K_{i}(q) и \{p,q\} \subseteq K_{i}\langle i\rangle или \{p,q\} \cap
K_{i}\langle i\rangle = \emptyset.

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

Литература

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