# Bandwidth

Перейти к:навигация, поиск

Bandwidthширина полосы.

Let $\,G = (V,E)$ be a simple graph and let $\,f$ be a numbering of vertices of $\,G$.

$B(G,f) = \max_{(u,v) \in E} |f(u) - f(v)|$

is called the bandwidth of the numbering $\,f$.

The bandwidth of $\,G$, denoted $\,B(G)$, is defined to be the minimum bandwidth of numberings of $\,G$.

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.

## Литература

• Евстигнеев В.А., Касьянов В.Н. Словарь по графам в информатике. — Новосибирск: Сибирское Научное Издательство, 2009.