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

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


Относительно обозначений см.  ''F-область''.
Относительно обозначений см.  ''[[F-Область|<math>\,F</math>-Область]]''.
==Литература==
==Литература==
[Касьянов/88],  
* Касьянов В.Н., Евстигнеев В.А. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


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

Текущая версия от 15:10, 27 ноября 2013

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

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

Литература

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