Линейное размещение графа

Линейное размещение графа (Linear layout of a graph) - для неориентированного графа отображение </math>L: \, V \longrightarrow \{0, 1, \ldots, |V|-1\}[math]\displaystyle{ . Разрезом графа }[/math]G[math]\displaystyle{ в точке }[/math]i[math]\displaystyle{ относительно '''Л.р.г.''' называется множество }[/math]C(G,L,i) = \{(u,v) \in E \, : \, 0 \leq L(u) < i \leq L(v) \leq |V|-1\}.[math]\displaystyle{ Шириной бисекции графа }[/math]G[math]\displaystyle{ называется величина }[/math]\min_{L}|C(G,L, \lfloor |V|/2 \rfloor)|.[math]\displaystyle{ Разрезающей шириной графа }[/math]G[math]\displaystyle{ называется величина }[/math]\min_{L}\max_{i}|C(G,L, i)|.[math]\displaystyle{ Другим функционалом является тотальная реберная длина графа }[/math]G[math]\displaystyle{ : }[/math]\min_{L} \sum_{(u,v) \in E} |L(u) - L(v)|.<math>

Литература

[WG'93]