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

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


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


* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.
* Евстигнеев В.А. Применение теории графов в программировании. — М.: Наука, 1985.

Версия от 15:09, 27 ноября 2013

Базисная нумерация (Basic numbering) — нумерация вершин графа, основанная на поиске в глубину. К базисным нумерациям относятся прямая нумерация (или [math]\displaystyle{ M }[/math]-нумерация), обратная нумерация (или [math]\displaystyle{ N }[/math]-нумерация). Для фиксированного обхода графа в глубину прямая нумерация определяется порядком первого попадания в вершины, а обратная — порядком, обратным порядку возврата из вершин.

Basic numbering.png

Литература

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