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

Материал из WEGA
Перейти к навигации Перейти к поиску

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