T-Нумерация

Материал из WikiGrapp
Версия для печати больше не поддерживается и может содержать ошибки обработки. Обновите закладки браузера и используйте вместо этого функцию печати браузера по умолчанию.

[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.