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

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


==Литература==
==Литература==
* Евстигнеев В. А., Касьянов В. Н. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.
* Касьянов В. Н., Евстигнеев В. А. Графы в программировании: обработка, визуализация и применение. — СПб.: БХВ-Петербург, 2003.


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

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

[math]\displaystyle{ \,T }[/math]-Нумерация ([math]\displaystyle{ \,T }[/math]-Numbering) — такая нумерация вершин уграфа, что для некоторой фиксированной его обратной нумерации [math]\displaystyle{ \,N }[/math] справедливы следующие свойства:

(1) для любых бивершин [math]\displaystyle{ \,p }[/math] и [math]\displaystyle{ \,q }[/math]: [math]\displaystyle{ \,T(p) \lt T(q) }[/math] тогда и только тогда, когда [math]\displaystyle{ \,N(p) \lt N(q) }[/math];

(2) [math]\displaystyle{ \,T }[/math]-номера вершин [math]\displaystyle{ \,N }[/math]-области [math]\displaystyle{ \,N[p] }[/math] вершины [math]\displaystyle{ \,p }[/math] образуют отрезок [math]\displaystyle{ \,[T(p),T(p)+|N[p]| - 1] }[/math].

T-Numbering.png

Литература

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