带宽 (图论)

图论中，图带宽问题是用不同整数给图G的n个顶点贴上标签，使得量最小化的问题（其中E是G的边集）。
这问题可以形象理解为，将图的顶点置于沿x轴的不同整数点上，使最长边最短的问题。这种放置称作线性图排列（linear graph arrangement）、线性图布局（linear graph layout）或线性图放置（linear graph placement）。

加权图带宽问题是广义化，其中边被赋权，需要最小化的损失函数为

就矩阵而言，（无权）图带宽是对称矩阵（图的邻接矩阵）的最小带宽。带宽也可定义为比给定图的紧合区间超图的最大团大小小1，其中超图最小化了团大小。

某些图的带宽公式
对部分图族，带宽有明确公式给出。

n顶点上的路径图的带宽是1，对于完全图我们有。对完全二分图，有

，其中

由Chvátal证明。A remark on a problem of Harary. V. Chvátal, Czechoslovak Mathematical Journal 20(1):109–111, 1970. http://dml.cz/dmlcz/100949 星图是此公式的特例，个顶点上的星图带宽为。

个顶点上的超立方图的带宽，确定为

Chvatálová证明Optimal Labelling of a product of two paths. J. Chvatálová, Discrete Mathematics 11, 249–253, 1975.，方格图（m、n个顶点上两个路径图之笛卡尔积）的带宽等于。

界
图的带宽可用各种图参数约束。例如，令表示G的色数：



令表示G的直径，则有不等式：

其中n是G中顶点数。

k带宽图G的径宽不大于k，其树深不大于。如上节所述，星图作为结构非常简单的树，带宽相对较大。注意的径宽为1，树深为2。

一些度有界图族具有亚线性带宽：证明，若T是最大度不大于∆的树，则

更一般地说，对最大度不大于∆的平面图，类似约束也成立（参）：

计算带宽
加与不加权的两类带宽计算问题都是二次瓶颈分配问题的特例。
带宽问题是NP困难的，即便对特例也如此。Garey–Johnson: GT40众所周知，带宽在任何常数范围内的近似都是NP难的，对最大毛长为2的毛虫树也如此。
对稠密图，设计了一种3近似算法。
另一方面，我们也知道一些多项式可解的特例。"Coping with the NP-Hardness of the Graph Bandwidth Problem", Uriel Feige, Lecture Notes in Computer Science, Volume 1851, 2000, pp. 129–145, Cuthill–McKee算法就是获得低带宽线图布局的启发式算法。图带宽计算的快速多层算法是在中提出的。

应用
对带宽问题的兴趣来自一些应用领域。

例如稀疏矩阵/带状矩阵处理与此领域的一般算法，如Cuthill–McKee算法，可用于寻找图带宽问题的近似解。

还有电子设计自动化。标准单元设计方法中，标准单元一般具有相同的高度，布局为若干行。这时，图带宽问题建模了将一组标准单元放置在单行中的问题，其目标是使最大传播延迟（假定与导线长度成正比）最小化。

另见
割宽与径宽

参考文献



外部链接
Minimum bandwidth problem , in: Pierluigi Crescenzi and Viggo Kann (eds.), A compendium of NP optimization problems. Accessed May 26, 2010.

Category:图算法
Category:组合优化
Category:NP困难问题
Category:图常量