Линейное размещение графа: различия между версиями

'''Линейное размещение графа''' (''[[Linear layout of a graph]]'') - для [[неориентированный граф|неориентированного графа]] отображение <math>L: \, V \longrightarrow \{0, 1, \ldots, |V|-1\}</math>. [[Разрез графа|Разрезом графа]] <math>G</math> в точке <math>i</math> относительно '''линейного размещения графа''' называется множество  

[[Разрезающая ширина графа|Разрезающей шириной графа]] <math>G</math> называется величина

<math>\min_{L}\max_{i}|C(G,L, i)|.</math>

Другим функционалом является [[тотальная реберная длина графа]] <math>G</math>:

<math>\min_{L} \sum_{(u,v) \in E} |L(u) - L(v)|.</math>