K-Нумерация

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

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

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

Литература

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

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