4624
правки
Bandwidth: различия между версиями
Перейти к навигации
Перейти к поиску
нет описания правки
Glk (обсуждение | вклад) (Новая страница: «'''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>. …») |
KEV (обсуждение | вклад) Нет описания правки |
||
| Строка 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. | |||