Ширина укладки

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

Ширина укладки (Width of an embedding) — пусть [math]\displaystyle{ \varphi(T) }[/math]укладка ордерева [math]\displaystyle{ \,T }[/math], дуги которого ориентированы к корню; дуга [math]\displaystyle{ \,(i,k) }[/math] проходит над [math]\displaystyle{ \,j }[/math], если [math]\displaystyle{ \,i \lt j \lt k }[/math]; если [math]\displaystyle{ w_{\varphi}(i,T) }[/math] — количество дуг, проходящих над [math]\displaystyle{ \,i }[/math] в укладке [math]\displaystyle{ \varphi }[/math], то ширина укладки есть величина [math]\displaystyle{ W(\varphi,T) }[/math], равная [math]\displaystyle{ \max_{i} w_{\varphi}(i,T) }[/math].

Литература

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