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

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

Навигация