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

Материал из WikiGrapp
Перейти к навигации Перейти к поиску
(Новая страница: «'''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: Строка 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.

Текущая версия от 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.