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

Материал из WEGA
Версия от 17:11, 16 февраля 2010; Glk (обсуждение | вклад) (Создана новая страница размером '''Ширина укладки''' (''Width of an embedding'') - пусть <math>\varphi(T)</math> --- ''укладка'' ордерев...)
(разн.) ← Предыдущая версия | Текущая версия (разн.) | Следующая версия → (разн.)

Ширина укладки (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].

Литература

[Евстигнеев/85]