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

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