Bandwidth

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.