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

Материал из WEGA
Перейти к навигации Перейти к поиску
(Создана новая страница размером '''Линейное размещение графа''' (''Linear layout of a graph'') - для неориентированного гр...)
 
Нет описания правки
 
(не показана 1 промежуточная версия этого же участника)
Строка 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> относительно '''линейного размещения графа''' называется множество  
для неориентированного графа отображение </math>L: \, V \longrightarrow
 
\{0, 1, \ldots, |V|-1\}<math>. Разрезом графа </math>G<math> в точке </math>i<math> относительно
<math>C(G,L,i) = \{(u,v) \in E \, : \, 0 \leq L(u) < i \leq L(v) \leq |V|-1\}.</math>
'''Л.р.г.''' называется множество
 
</math>C(G,L,i) = \{(u,v) \in E \, : \, 0 \leq L(u) < i \leq L(v) \leq
[[Ширина бисекции графа|Шириной бисекции графа]] <math>G</math> называется величина  
|V|-1\}.<math>
 
Шириной бисекции графа </math>G<math> называется величина
<math>\min_{L}|C(G,L, \lfloor |V|/2 \rfloor)|.</math>
</math>\min_{L}|C(G,L, \lfloor |V|/2 \rfloor)|.<math>
 
Разрезающей шириной графа </math>G<math> называется величина
[[Разрезающая ширина графа|Разрезающей шириной графа]] <math>\,G</math> называется величина
</math>\min_{L}\max_{i}|C(G,L, i)|.<math>
<math>\,\min_{L}\max_{i}|C(G,L, i)|.</math>
Другим функционалом является тотальная реберная длина графа </math>G<math>:
Другим функционалом является [[тотальная реберная длина графа]] <math>\,G</math>:
</math>\min_{L} \sum_{(u,v) \in E} |L(u) - L(v)|.<math>
 
<math>\,\min_{L} \sum_{(u,v) \in E} |L(u) - L(v)|.</math>
 
==Литература==
==Литература==
[WG'93]
* Workshop. Utrecht, 1993 // Lect. Notes Comp. Sci., 1994, vol. 790.

Текущая версия от 13:25, 29 апреля 2011

Линейное размещение графа (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.