带宽 (图论)

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

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

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

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

${\displaystyle 2^{n}}$个顶点上的超立方图${\displaystyle Q_{n}}$的带宽，Harper (1966)确定为

${\displaystyle \varphi (Q_{n})=\sum _{m=0}^{n-1}{\binom {m}{\lfloor m/2\rfloor }}.}$

Chvatálová证明[4]，${\displaystyle m\times n}$方格图${\displaystyle P_{m}\times P_{n}}$（m、n个顶点上两个路径图之笛卡尔积）的带宽等于${\displaystyle {\rm {min}}\{m,\ n\}}$。

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

${\displaystyle \varphi (G)\geq \chi (G)-1;}$

令${\displaystyle {\rm {diam}}(G)}$表示G的直径，则有不等式：[5]

${\displaystyle \lceil (n-1)/\operatorname {diam} (G)\rceil \leq \varphi (G)\leq n-\operatorname {diam} (G),}$

其中n是G中顶点数。

k带宽图G的径宽不大于k（Kaplan & Shamir 1996），其树深不大于${\displaystyle k\log(n/k)}$（Gruber 2012）。如上节所述，星图${\displaystyle S_{k}}$作为结构非常简单的树，带宽相对较大。注意${\displaystyle S_{k}}$的径宽为1，树深为2。

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

${\displaystyle \varphi (T)\leq {\frac {5n}{\log _{\Delta }n}}.}$

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

${\displaystyle \varphi (G)\leq {\frac {20n}{\log _{\Delta }n}}.}$

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

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

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

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

• 割宽与径宽

• Böttcher, J.; Pruessmann, K. P.; Taraz, A.; Würfl, A. . European Journal of Combinatorics. 2010, 31 (5): 1217–1227. arXiv:0910.3014 . doi:10.1016/j.ejc.2009.10.010.
• Chinn, P. Z.; Chvátalová, J.; Dewdney, A. K.; Gibbs, N. E. . Journal of Graph Theory. 1982, 6 (3): 223–254. doi:10.1002/jgt.3190060302.
• Chung, Fan R. K., , Beineke, Lowell W.; Wilson, Robin J. (编), (PDF), Academic Press: 151–168, 1988, ISBN 978-0-12-086203-0
• Dubey, C.; Feige, U.; Unger, W. . Journal of Computer and System Sciences. 2010, 77: 62–90. doi:10.1016/j.jcss.2010.06.006 .
• Garey, M.R.; Johnson, D.S. . New York: W.H. Freeman. 1979. ISBN 0-7167-1045-5.
• Gruber, Hermann, , Journal of Combinatorics, 2012, 3 (4): 669–682, arXiv:1012.1344 , doi:10.4310/joc.2012.v3.n4.a5
• Harper, L. . Journal of Combinatorial Theory. 1966, 1 (3): 385–393. doi:10.1016/S0021-9800(66)80059-5 .
• Kaplan, Haim; Shamir, Ron, , SIAM Journal on Computing, 1996, 25 (3): 540–561, doi:10.1137/s0097539793258143
• Karpinski, Marek; Wirtgen, Jürgen; Zelikovsky, Aleksandr. . Electronic Colloquium on Computational Complexity. 1997, 4 (17).

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