Аноним

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:
'''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>.




Строка 15: Строка 15:
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.