L-Нумерация: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''L-Нумерация''' (''L-Numbering'') - ''нумерация вершин'' уграфа <math>G</math>, которая опред...)
 
Нет описания правки
 
(не показаны 2 промежуточные версии этого же участника)
Строка 1: Строка 1:
'''L-Нумерация''' (''L-Numbering'') -
'''<math>\,L</math>-Нумерация''' (''[[L-Numbering|<math>\,L</math>-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-Область|<math>\,F</math>-Область]]'' и  ''[[F-Ранг|<math>F\,</math>-Ранг]]''.
==Литература==
==Литература==
[Касьянов/88],  
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


[Евстигнеев-Касьянов/94]
* Касьянов В.Н. Оптимизирующие преобразования программ. — М.: Наука, 1988.

Текущая версия от 11:54, 20 мая 2011

[math]\displaystyle{ \,L }[/math]-Нумерация ([math]\displaystyle{ \,L }[/math]-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].

Относительно обозначений см. [math]\displaystyle{ \,F }[/math]-Область и [math]\displaystyle{ F\, }[/math]-Ранг.

Литература

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