Bandwidth: различия между версиями
KEV (обсуждение | вклад) Нет описания правки |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 1: | Строка 1: | ||
'''Bandwidth''' — ''[[ширина полосы]].'' | '''Bandwidth''' — ''[[ширина полосы]].'' | ||
Let <math>G = (V,E)</math> be a [[simple graph]] | Let <math>\,G = (V,E)</math> be a [[simple graph]] | ||
and let <math>f</math> be a numbering of [[vertex|vertices]] of <math>G</math>. | and let <math>\,f</math> be a numbering of [[vertex|vertices]] of <math>\,G</math>. | ||
<math>B(G,f) = \max_{(u,v) \in E} |f(u) - f(v)|</math> | <math>B(G,f) = \max_{(u,v) \in E} |f(u) - f(v)|</math> | ||
is called the '''bandwidth''' of the numbering <math>f</math>. | is called the '''bandwidth''' of the numbering <math>\,f</math>. | ||
The '''bandwidth''' of <math>G</math>, denoted | The '''bandwidth''' of <math>\,G</math>, denoted | ||
<math>B(G)</math>, is defined to be the minimum bandwidth of numberings of <math>G</math>. | <math>\,B(G)</math>, is defined to be the minimum bandwidth of numberings of <math>\,G</math>. | ||
The bandwidth problem for graphs has attracted many graph theorists | The bandwidth problem for graphs has attracted many graph theorists | ||
Текущая версия от 17:24, 21 декабря 2011
Bandwidth — ширина полосы.
Let [math]\displaystyle{ \,G = (V,E) }[/math] be a simple graph and let [math]\displaystyle{ \,f }[/math] be a numbering of vertices of [math]\displaystyle{ \,G }[/math].
[math]\displaystyle{ B(G,f) = \max_{(u,v) \in E} |f(u) - f(v)| }[/math]
is called the bandwidth of the numbering [math]\displaystyle{ \,f }[/math].
The bandwidth of [math]\displaystyle{ \,G }[/math], denoted [math]\displaystyle{ \,B(G) }[/math], is defined to be the minimum bandwidth of numberings of [math]\displaystyle{ \,G }[/math].
The bandwidth problem for graphs has attracted many graph theorists for its strong practical background and theoretical interest. The decision problem for finding the bandwidths of arbitrary graphs is NP-complete, even for trees having the maximum degree 3, caterpillars with hairs of length at most 3 and cobipartite graphs. The problem is polynomially solvable for caterpillars with hairs of length 1 and 2, cographs, and interval graphs.
See also
Литература
- Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.