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

Материал из WikiGrapp
Перейти к:навигация, поиск

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

Литература

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