带宽 (图论)

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

加权图带宽问题是广义化，其中边被赋权$w_{ij}$，需要最小化的损失函数为$\max \{w_{ij}|f(v_i)-f(v_j)|:v_i{v}_j\in E\}.$

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

某些图的带宽公式

对部分图族，带宽$\phi (G)$有明确公式给出。

n顶点上的路径图$P_n$的带宽是1，对于完全图$K_m$我们有$\phi (K_n)=n-1$。对完全二分图$K_{m,n}$，有

$\phi (K_{m,n})=\lfloor (m-1)/2\rfloor +n$，其中$m\ge n\ge 1,$

由Chvátal证明。星图$S_k=K_{k,1}$是此公式的特例，$k+1$个顶点上的星图带宽为$\phi (S_k)=\lfloor (k-1)/2\rfloor +1$。

$2^n$个顶点上的超立方图$Q_n$的带宽，Template:Harvtxt确定为

$\phi (Q_n)=\sum _{m=0}^{n-1}(\genfrac{}{}{0ex}{}{m}{\lfloor m/2\rfloor }).$

Chvatálová证明，$m\times n$方格图$P_m\times P_n$（m、n个顶点上两个路径图之笛卡尔积）的带宽等于$\mathrm{m}\mathrm{i}\mathrm{n}\{m,n\}$。

界

图的带宽可用各种图参数约束。例如，令$\chi (G)$表示G的色数：

$\phi (G)\ge \chi (G)-1;$

令$\mathrm{d}\mathrm{i}\mathrm{a}\mathrm{m}(G)$表示G的直径，则有不等式：

$\lceil (n-1)/\mathrm{diam}(G)\rceil \le \phi (G)\le n-\mathrm{diam}(G),$

其中n是G中顶点数。

k带宽图G的径宽不大于kTemplate:Harv，其树深不大于$k\log (n/k)$Template:Harv。如上节所述，星图$S_k$作为结构非常简单的树，带宽相对较大。注意$S_k$的径宽为1，树深为2。

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

$\phi (T)\le \frac{5n}{{\log }_{\mathrm{\Delta }}n}.$

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

$\phi (G)\le \frac{20n}{{\log }_{\mathrm{\Delta }}n}.$

计算带宽

加与不加权的两类带宽计算问题都是二次瓶颈分配问题的特例。 带宽问题是NP困难的，即便对特例也如此。众所周知，带宽在任何常数范围内的近似都是NP难的，对最大毛长为2的毛虫树也如此Template:Harv。 对稠密图，Template:Harvtxt设计了一种3近似算法。 另一方面，我们也知道一些多项式可解的特例。Cuthill–McKee算法就是获得低带宽线图布局的启发式算法。图带宽计算的快速多层算法是在中提出的。

应用

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

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

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

另见

• 割宽与径宽

参考文献

• Template:Cite journal
• Template:Cite journal
• Template:Citation
• Template:Cite journal
• Template:Cite book
• Template:Citation
• Template:Cite journal
• Template:Citation
• Template:Cite journal

外部链接

• Minimum bandwidth problem Template:Wayback, in: Pierluigi Crescenzi and Viggo Kann (eds.), A compendium of NP optimization problems. Accessed May 26, 2010.