Bandwidth

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

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.

See also

Литература

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