Линейное размещение графа: различия между версиями
Glk (обсуждение | вклад) (Создана новая страница размером '''Линейное размещение графа''' (''Linear layout of a graph'') - для неориентированного гр...) |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Линейное размещение графа''' (''Linear layout of a graph'') - | '''Линейное размещение графа''' (''[[Linear layout of a graph]]'') - для [[неориентированный граф|неориентированного графа]] отображение <math>L: \, V \longrightarrow \{0, 1, \ldots, |V|-1\}</math>. [[Разрез графа|Разрезом графа]] <math>G</math> в точке <math>i</math> относительно '''линейного размещения графа''' называется множество | ||
для неориентированного графа отображение < | |||
\{0, 1, \ldots, |V|-1\}<math>. Разрезом графа < | <math>C(G,L,i) = \{(u,v) \in E \, : \, 0 \leq L(u) < i \leq L(v) \leq |V|-1\}.</math> | ||
''' | |||
< | [[Ширина бисекции графа|Шириной бисекции графа]] <math>G</math> называется величина | ||
|V|-1\}.<math> | |||
Шириной бисекции графа < | <math>\min_{L}|C(G,L, \lfloor |V|/2 \rfloor)|.</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> | |||
==Литература== | ==Литература== | ||
[WG'93] | [WG'93] | ||
Версия от 11:34, 20 ноября 2009
Линейное размещение графа (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]
Литература
[WG'93]