图论中，图带宽问题是用不同整数f(v_i)给图G的n个顶点v_i贴上标签，使得量\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}最小化的问题（其中E是G的边集）。
这问题可以形象理解为，将图的顶点置于沿x轴的不同整数点上，使最长边最短的问题。这种放置称作线性图排列（linear graph arrangement）、线性图布局（linear graph layout）或线性图放置（linear graph placement）。星图S_k = K_{k,1}是此公式的特例，k+1个顶点上的星图带宽为\varphi(S_{k}) = \lfloor (k-1)/2\rfloor+1。
2^n个顶点上的超立方图Q_n的带宽，确定为
:\varphi(Q_n)=\sum_{m=0}^{n-1} \binom{m}{\lfloor m/2\rfloor}.
Chvatálová证明，m\times n方格图P_m \times P_n（m、n个顶点上两个路径图之笛卡尔积）的带宽等于{\rm min}\{m,\ n\}。
界
图的带宽可用各种图参数约束。例如，令\chi(G)表示G的色数：
: \varphi(G) \ge \chi(G) - 1;
令{\rm diam}(G)表示G的直径，则有不等式：
:\lceil (n-1)/\operatorname{diam}(G) \rceil \le \varphi(G) \le n - \operatorname{diam}(G),
其中n是G中顶点数。
k带宽图G的径宽不大于k，其树深不大于k\log(n/k)。如上节所述，星图S_k作为结构非常简单的树，带宽相对较大。注意S_k的径宽为1，树深为2。
一些度有界图族具有亚线性带宽：证明，若T是最大度不大于∆的树，则
:\varphi(T) \le \frac{5n}{\log_\Delta n}.
更一般地说，对最大度不大于∆的平面图，类似约束也成立（参）：
:\varphi(G) \le \frac{20n}{\log_\Delta n}.
计算带宽
加与不加权的两类带宽计算问题都是二次瓶颈分配问题的特例。
带宽问题是NP困难的，即便对特例也如此。众所周知，带宽在任何常数范围内的近似都是NP难的，对最大毛长为2的毛虫树也如此。
对稠密图，设计了一种3近似算法。
另一方面，我们也知道一些多项式可解的特例。Cuthill–McKee算法就是获得低带宽线图布局的启发式算法。图带宽计算的快速多层算法是在中提出的。
应用
对带宽问题的兴趣来自一些应用领域。
例如稀疏矩阵/带状矩阵处理与此领域的一般算法，如Cuthill–McKee算法，可用于寻找图带宽问题的近似解。
还有电子设计自动化。标准单元设计方法中，标准单元一般具有相同的高度，布局为若干行。这时，图带宽问题建模了将一组标准单元放置在单行中的问题，其目标是使最大传播延迟（假定与导线长度成正比）最小化。
另见
*割宽与径宽
参考文献
*
*
*
*
*
*
*
*
*
外部链接
[http://www.csc.kth.se/~viggo/wwwcompendium/node53.html Minimum bandwidth problem] , in: Pierluigi Crescenzi and Viggo Kann (eds.), A compendium of NP optimization problems.* Accessed May 26, 2010.
评论 (0)