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>. …»)
(нет различий)

Версия от 15:42, 17 февраля 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

  • Layout, Graceful graph.