Аноним

Bandwidth: различия между версиями

Материал из WEGA
нет описания правки
(Новая страница: «'''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>. …»)
 
Нет описания правки
 
Строка 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>.




<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
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.