带宽 (图论)

图论中,图带宽问题是用不同整数Gn顶点贴上标签,使得量最小化的问题(其中EG的边集)。[1] 这问题可以形象理解为,将图的顶点置于沿x轴的不同整数点上,使最长边最短的问题。这种放置称作线性图排列(linear graph arrangement)、线性图布局(linear graph layout)或线性图放置(linear graph placement)。[2]

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

就矩阵而言,(无权)图带宽是对称矩阵(图的邻接矩阵)的最小带宽。带宽也可定义为比给定图的紧合区间超图的最大大小小1,其中超图最小化了团大小。(Kaplan & Shamir 1996)

某些图的带宽公式

对部分图族,带宽 有明确公式给出。

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

 ,其中 

由Chvátal证明。[3]星图 是此公式的特例, 个顶点上的星图带宽为 

 个顶点上的超立方图 的带宽,Harper (1966)确定为

 

Chvatálová证明[4] 格图 mn个顶点上两个路径图之笛卡尔积)的带宽等于 

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

 

 表示G直径,则有不等式:[5]

 

其中nG中顶点数。

k带宽图G径宽不大于k(Kaplan & Shamir 1996),其树深不大于 (Gruber 2012)。如上节所述,星图 作为结构非常简单的,带宽相对较大。注意 径宽为1,树深为2。

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

 

更一般地说,对最大度不大于∆的平面图,类似约束也成立(参Böttcher et al. 2010):

 

计算带宽

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

应用

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

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

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

另见

参考文献

  1. ^ (Chinn et al. 1982)
  2. ^ 2.0 2.1 "Coping with the NP-Hardness of the Graph Bandwidth Problem", Uriel Feige, Lecture Notes in Computer Science, Volume 1851, 2000, pp. 129-145, doi:10.1007/3-540-44985-X_2
  3. ^ A remark on a problem of Harary. V. Chvátal, Czechoslovak Mathematical Journal 20(1):109–111, 1970. http://dml.cz/dmlcz/100949页面存档备份,存于互联网档案馆
  4. ^ Optimal Labelling of a product of two paths. J. Chvatálová, Discrete Mathematics 11, 249–253, 1975.
  5. ^ Chinn et al. 1982
  6. ^ Garey–Johnson: GT40
  7. ^ Ilya Safro and Dorit Ron and Achi Brandt. Multilevel Algorithms for Linear Ordering Problems. ACM Journal of Experimental Algorithmics. 2008, 13: 1.4–1.20. doi:10.1145/1412228.1412232. 

外部链接