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

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

[math]\displaystyle{ C(G,L,i) = \{(u,v) \in E \, : \, 0 \leq L(u) \lt i \leq L(v) \leq |V|-1\}. }[/math]

Шириной бисекции графа [math]\displaystyle{ G }[/math] называется величина

[math]\displaystyle{ \min_{L}|C(G,L, \lfloor |V|/2 \rfloor)|. }[/math]

Разрезающей шириной графа [math]\displaystyle{ \,G }[/math] называется величина [math]\displaystyle{ \,\min_{L}\max_{i}|C(G,L, i)|. }[/math] Другим функционалом является тотальная реберная длина графа [math]\displaystyle{ \,G }[/math]:

[math]\displaystyle{ \,\min_{L} \sum_{(u,v) \in E} |L(u) - L(v)|. }[/math]

Литература

• Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790.