带宽 (图论)
图论中,图带宽问题是用不同整数给图G的n个顶点贴上标签,使得量最小化的问题(其中E是G的边集)。[1] 这问题可以形象理解为,将图的顶点置于沿x轴的不同整数点上,使最长边最短的问题。这种放置称作线性图排列(linear graph arrangement)、线性图布局(linear graph layout)或线性图放置(linear graph placement)。[2]
加权图带宽问题是广义化,其中边被赋权,需要最小化的损失函数为
就矩阵而言,(无权)图带宽是对称矩阵(图的邻接矩阵)的最小带宽。带宽也可定义为比给定图的紧合区间超图的最大团大小小1,其中超图最小化了团大小。(Kaplan & Shamir 1996)
某些图的带宽公式
对部分图族,带宽 有明确公式给出。
n顶点上的路径图 的带宽是1,对于完全图 我们有 。对完全二分图 ,有
- ,其中
由Chvátal证明。[3]星图 是此公式的特例, 个顶点上的星图带宽为 。
个顶点上的超立方图 的带宽,Harper (1966)确定为
界
图的带宽可用各种图参数约束。例如,令 表示G的色数:
其中n是G中顶点数。
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算法,可用于寻找图带宽问题的近似解。
还有电子设计自动化。标准单元设计方法中,标准单元一般具有相同的高度,布局为若干行。这时,图带宽问题建模了将一组标准单元放置在单行中的问题,其目标是使最大传播延迟(假定与导线长度成正比)最小化。
另见
参考文献
- ^ (Chinn 等人 1982)
- ^ 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
- ^ A remark on a problem of Harary. V. Chvátal, Czechoslovak Mathematical Journal 20(1):109–111, 1970. http://dml.cz/dmlcz/100949 (页面存档备份,存于互联网档案馆)
- ^ Optimal Labelling of a product of two paths. J. Chvatálová, Discrete Mathematics 11, 249–253, 1975.
- ^ Chinn et al. 1982
- ^ Garey–Johnson: GT40
- ^ 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.
- Böttcher, J.; Pruessmann, K. P.; Taraz, A.; Würfl, A. Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs. 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. The bandwidth problem for graphs and matrices—a survey. Journal of Graph Theory. 1982, 6 (3): 223–254. doi:10.1002/jgt.3190060302.
- Chung, Fan R. K., Labelings of Graphs, Beineke, Lowell W.; Wilson, Robin J. (编), Selected Topics in Graph Theory (PDF), Academic Press: 151–168, 1988 [2024-01-31], ISBN 978-0-12-086203-0, (原始内容存档 (PDF)于2018-10-25)
- Dubey, C.; Feige, U.; Unger, W. Hardness results for approximating the bandwidth. Journal of Computer and System Sciences. 2010, 77: 62–90. doi:10.1016/j.jcss.2010.06.006 .
- Garey, M.R.; Johnson, D.S. Computers and Intractability: A Guide to the Theory of NP-Completeness. New York: W.H. Freeman. 1979. ISBN 0-7167-1045-5.
- Gruber, Hermann, On Balanced Separators, Treewidth, and Cycle Rank, Journal of Combinatorics, 2012, 3 (4): 669–682, arXiv:1012.1344 , doi:10.4310/joc.2012.v3.n4.a5
- Harper, L. Optimal numberings and isoperimetric problems on graphs. Journal of Combinatorial Theory. 1966, 1 (3): 385–393. doi:10.1016/S0021-9800(66)80059-5 .
- Kaplan, Haim; Shamir, Ron, Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques, SIAM Journal on Computing, 1996, 25 (3): 540–561, doi:10.1137/s0097539793258143
- Karpinski, Marek; Wirtgen, Jürgen; Zelikovsky, Aleksandr. An Approximation Algorithm for the Bandwidth Problem on Dense Graphs. Electronic Colloquium on Computational Complexity. 1997, 4 (17) [2024-01-31]. (原始内容存档于2013-06-19).
外部链接
- Minimum bandwidth problem (页面存档备份,存于互联网档案馆), in: Pierluigi Crescenzi and Viggo Kann (eds.), A compendium of NP optimization problems. Accessed May 26, 2010.