F-Ранг

Материал из WEGA
Версия от 13:25, 14 июля 2011; KEV (обсуждение | вклад)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)
Перейти к навигации Перейти к поиску

[math]\displaystyle{ \,F }[/math]-Ранг ([math]\displaystyle{ \,F }[/math]-Rank) — Пусть [math]\displaystyle{ \,F }[/math] — некоторая нумерация уграфа [math]\displaystyle{ \,G }[/math] и [math]\displaystyle{ i,j\in [1,n] }[/math], где [math]\displaystyle{ \,n }[/math] — число вершин в [math]\displaystyle{ \,G }[/math]. [math]\displaystyle{ \,F }[/math]-ранг вершины [math]\displaystyle{ \,q }[/math] в [math]\displaystyle{ \,[i,j] }[/math] равен [math]\displaystyle{ \max (1,\{F(p):p\in A\}) }[/math], где [math]\displaystyle{ \,A }[/math] — множество всех тех вершин [math]\displaystyle{ \,F }[/math]-линии в [math]\displaystyle{ \,[i,j] }[/math], из которых [math]\displaystyle{ \,F }[/math]-достижима вершина [math]\displaystyle{ \,q }[/math].

Литература

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