Bandwidth: различия между версиями
Glk (обсуждение | вклад) (Новая страница: «'''Bandwidth''' --- ширина полосы. Let <math>G = (V,E)</math> be a simple graph and let <math>f</math> be a numbering of vertices of <math>G</math>. …») |
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 vertices of <math>G</math>. | and let <math>f</math> be a numbering of [[vertex|vertices]] of <math>G</math>. | ||
| Строка 15: | Строка 15: | ||
for its strong practical background and theoretical interest. | for its strong practical background and theoretical interest. | ||
The decision problem for finding the bandwidths of arbitrary graphs is | 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 | NP-complete, even for [[tree|trees]] having the maximum degree 3, ''[[caterpillar|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''. | hairs of length 1 and 2, ''[[cograph|cographs]]'', and ''[[interval graph|interval graphs]]''. | ||
==See also== | ==See also== | ||
*''Layout'', ''Graceful graph''. | * ''[[Layout]]'', | ||
* ''[[Graceful graph]]''. | |||
==Литература== | |||
* Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009. | |||
Версия от 17:22, 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.