Разумная нумерация: различия между версиями

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Разумная нумерация''' (''Reasonable numbering'') - такая нумерация <math>F</math> уграфа <math>G<...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 1: Строка 1:
'''Разумная нумерация''' (''Reasonable numbering'') -
'''Разумная нумерация''' (''[[Reasonable numbering]]'') такая [[нумерация вершин|нумерация]] <math>\,F</math> [[уграф|уграфа]] <math>\,G</math>, что справедливы два свойства:
такая нумерация <math>F</math> уграфа <math>G</math>, что справедливы два свойства:


(1)
(1) <math>F(p)\leq  F(q)</math> для любых [[вершина|вершин]] <math>\,p</math> и <math>\,q</math> таких, что <math>\,p</math> обязательно предшествует <math>\,q</math>;
<math>F(p)\leq  F(q)</math> для любых вершин
 
<math>p</math> и <math>q</math> таких, что <math>p</math> обязательно предшествует <math>q</math>;
(2) если <math>\,G</math> — [[аранжируемый граф|аранжируемый уграф]], то <math>\,F</math> является [[аранжировка|аранжировкой]].


(2) если <math>G</math> ---
аранжируемый уграф, то <math>F</math> является аранжировкой.
==Литература==
==Литература==
[Касьянов/88],


[Евстигнеев/85],
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
 
* Евстигнеев В.А., Касьянов В.Н. Теория графов: алгоритмы обработки деревьев. — Новосибирск: Наука. Сиб. отд-ние, 1994.


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

Текущая версия от 13:14, 14 июля 2011

Разумная нумерация (Reasonable numbering) — такая нумерация [math]\displaystyle{ \,F }[/math] уграфа [math]\displaystyle{ \,G }[/math], что справедливы два свойства:

(1) [math]\displaystyle{ F(p)\leq F(q) }[/math] для любых вершин [math]\displaystyle{ \,p }[/math] и [math]\displaystyle{ \,q }[/math] таких, что [math]\displaystyle{ \,p }[/math] обязательно предшествует [math]\displaystyle{ \,q }[/math];

(2) если [math]\displaystyle{ \,G }[/math]аранжируемый уграф, то [math]\displaystyle{ \,F }[/math] является аранжировкой.

Литература

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