L-Нумерация: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''L-Нумерация''' (''L-Numbering'') - ''нумерация вершин'' уграфа <math>G</math>, которая опред...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''L-Нумерация''' (''L-Numbering'') - | '''L-Нумерация''' (''[[L-Numbering]]'') - | ||
''нумерация вершин'' уграфа <math>G</math>, которая определяется как последний член | ''[[нумерация вершин]]'' [[уграф|уграфа]] <math>G</math>, которая определяется как последний член | ||
<math>L_{0}</math>последовательности нумераций <math>L_{n}, \; L_{n-1}, \; | <math>L_{0}</math> последовательности нумераций <math>L_{n}, \; L_{n-1}, \; | ||
\ldots, \; L_{0}</math> в которой <math>L_{n}</math>есть <math>K</math>-нумерация и для | \ldots, \; L_{0}</math> в которой <math>L_{n}</math> есть [[K-Нумерация|<math>K</math>-нумерация]] и для | ||
любых вершин <math>p, \; q</math> и номера <math>i</math> справедливы следующие два | любых вершин <math>p, \; q</math> и номера <math>i</math> справедливы следующие два | ||
свойства: если <math>L_{i}(p) < i</math> или <math>L_{i}(p) > i + |L_{i}\langle i\rangle|</math>, | свойства: если <math>L_{i}(p) < i</math> или <math>L_{i}(p) > i + |L_{i}\langle i\rangle|</math>, | ||
то <math>L_{i-1}(p) = L_{i}(p)</math>; если <math>L_{i}(p), \; L_{i}(q) \in | то <math>L_{i-1}(p) = L_{i}(p)</math>; если <math>L_{i}(p), \; L_{i}(q) \in | ||
[i, i+|L_{i}\langle i\rangle |)</math>, то <math>L_{i-1}(p) < L_{i-1}(q)</math> тогда и только | [i, i+|L_{i}\langle i\rangle |)</math>, то <math>L_{i-1}(p) < L_{i-1}(q)</math> тогда и только | ||
тогда, когда либо <math>p</math> и <math>q</math> имеют один и тот же <math>L_{i}</math>''ранг'' в | тогда, когда либо <math>p</math> и <math>q</math> имеют один и тот же <math>L_{i}</math>-''ранг'' в | ||
<math>[i,i + |L_{i}\langle i\rangle |)</math> и <math>L_{i}(p) < L_{i}(q)</math>, либо | <math>[i,i + |L_{i}\langle i\rangle |)</math> и <math>L_{i}(p) < L_{i}(q)</math>, либо | ||
<math>L_{i}</math>ранг вершины <math>q</math> превышает <math>L_{i}</math>ранг вершины <math>p</math> в | <math>L_{i}</math>-ранг [[вершина|вершины]] <math>q</math> превышает <math>L_{i}</math>-ранг вершины <math>p</math> в | ||
<math>[i,i+|L_{i}\langle i\rangle |)</math>. | <math>[i,i+|L_{i}\langle i\rangle |)</math>. | ||
Относительно обозначений см. ''F-Область'' и ''F-Ранг''. | Относительно обозначений см. ''[[F-Область]]'' и ''[[F-Ранг]]''. | ||
==Литература== | ==Литература== | ||
[Касьянов/88], | [Касьянов/88], | ||
[Евстигнеев-Касьянов/94] | [Евстигнеев-Касьянов/94] | ||
Версия от 19:41, 25 ноября 2009
L-Нумерация (L-Numbering) - нумерация вершин уграфа [math]\displaystyle{ G }[/math], которая определяется как последний член [math]\displaystyle{ L_{0} }[/math] последовательности нумераций [math]\displaystyle{ L_{n}, \; L_{n-1}, \; \ldots, \; L_{0} }[/math] в которой [math]\displaystyle{ L_{n} }[/math] есть [math]\displaystyle{ K }[/math]-нумерация и для любых вершин [math]\displaystyle{ p, \; q }[/math] и номера [math]\displaystyle{ i }[/math] справедливы следующие два свойства: если [math]\displaystyle{ L_{i}(p) \lt i }[/math] или [math]\displaystyle{ L_{i}(p) \gt i + |L_{i}\langle i\rangle| }[/math], то [math]\displaystyle{ L_{i-1}(p) = L_{i}(p) }[/math]; если [math]\displaystyle{ L_{i}(p), \; L_{i}(q) \in [i, i+|L_{i}\langle i\rangle |) }[/math], то [math]\displaystyle{ L_{i-1}(p) \lt L_{i-1}(q) }[/math] тогда и только тогда, когда либо [math]\displaystyle{ p }[/math] и [math]\displaystyle{ q }[/math] имеют один и тот же [math]\displaystyle{ L_{i} }[/math]-ранг в [math]\displaystyle{ [i,i + |L_{i}\langle i\rangle |) }[/math] и [math]\displaystyle{ L_{i}(p) \lt L_{i}(q) }[/math], либо [math]\displaystyle{ L_{i} }[/math]-ранг вершины [math]\displaystyle{ q }[/math] превышает [math]\displaystyle{ L_{i} }[/math]-ранг вершины [math]\displaystyle{ p }[/math] в [math]\displaystyle{ [i,i+|L_{i}\langle i\rangle |) }[/math].
Относительно обозначений см. F-Область и F-Ранг.
Литература
[Касьянов/88],
[Евстигнеев-Касьянов/94]