查看“︁带宽 (图论)”︁的源代码

[[图论]]中，'''图带宽问题'''是用不同[[整数]]<math>f(v_i)</math>给[[图 (数学)|图]]''G''的''n''个[[顶点 (图论)|顶点]]<math>v_i</math>贴上标签，使得量<math>\max\{\,| f(v_i) - f(v_j)| : v_iv_j \in E \,\}</math>最小化的问题（其中''E''是''G''的边集）。<ref>{{harv|Chinn|Chvátalová|Dewdney|Gibbs|1982}}</ref>
这问题可以形象理解为，将图的顶点置于沿''x''轴的不同整数点上，使最长边最短的问题。这种放置称作'''线性图排列'''（linear graph arrangement）、'''线性图布局'''（linear graph layout）或'''线性图放置'''（linear graph placement）。<ref name=feige/>

'''加权图带宽问题'''是[[广义化]]，其中边被赋[[图_(数学)#赋权图|权]]<math>w_{ij}</math>，需要最小化的[[损失函数]]为<math>\max\{\, w_{ij} |f(v_i) - f(v_j)| : v_iv_j \in E \,\}.</math>

就矩阵而言，（无权）图带宽是[[对称矩阵]]（图的[[邻接矩阵]]）的最小[[带状矩阵|带宽]]。带宽也可定义为比给定图的[[无差图|紧合区间]]超图的最大[[团 (图论)|团]]大小小1，其中超图最小化了团大小。{{harv|Kaplan|Shamir|1996}}

==某些图的带宽公式==
对部分图族，带宽<math>\varphi(G)</math>有明确公式给出。

''n''顶点上的路径图<math>P_n</math>的带宽是1，对于完全图<math>K_m</math>我们有<math>\varphi(K_n)=n-1</math>。对[[完全二分图]]<math>K_{m,\ n}</math>，有

:<math>\varphi(K_{m,n}) = \lfloor (m-1)/2\rfloor+n</math>，其中<math>m \ge n\ge 1,</math>

由Chvátal证明。<ref>A remark on a problem of Harary. V. Chvátal, ''Czechoslovak Mathematical Journal'' '''20'''(1):109&ndash;111, 1970. [http://dml.cz/dmlcz/100949 http://dml.cz/dmlcz/100949] {{Wayback|url=http://dml.cz/dmlcz/100949 |date=20160303193407 }}</ref>[[星 (图论)|星图]]<math>S_k = K_{k,1}</math>是此公式的特例，<math>k+1</math>个顶点上的星图带宽为<math>\varphi(S_{k}) = \lfloor (k-1)/2\rfloor+1</math>。

<math>2^n</math>个顶点上的[[超立方图]]<math>Q_n</math>的带宽，{{harvtxt|Harper|1966}}确定为
:<math>\varphi(Q_n)=\sum_{m=0}^{n-1} \binom{m}{\lfloor m/2\rfloor}.</math>

Chvatálová证明<ref>Optimal Labelling of a product of two paths. J. Chvatálová, ''Discrete Mathematics'' '''11''', 249&ndash;253, 1975.</ref>，<math>m\times n</math>方[[格图]]<math>P_m \times P_n</math>（''m''、''n''个顶点上两个路径图之[[图的笛卡尔积|笛卡尔积]]）的带宽等于<math>{\rm min}\{m,\ n\}</math>。

==界==
图的带宽可用各种图参数约束。例如，令<math>\chi(G)</math>表示''G''的[[图着色问题#图色数|色数]]：

: <math> \varphi(G) \ge \chi(G) - 1; </math>

令<math>{\rm diam}(G)</math>表示''G''的[[距离_(图论)#相关概念|直径]]，则有不等式：<ref>{{harvnb|Chinn|Chvátalová|Dewdney|Gibbs|1982}}</ref>

:<math>\lceil (n-1)/\operatorname{diam}(G) \rceil \le \varphi(G) \le n - \operatorname{diam}(G),</math>

其中''n''是''G''中顶点数。

''k''带宽图''G''的[[径宽]]不大于''k''{{harv|Kaplan|Shamir|1996}}，其[[树深]]不大于<math>k\log(n/k)</math>{{harv|Gruber|2012}}。如上节所述，星图<math>S_k</math>作为结构非常简单的[[树 (图论)|树]]，带宽相对较大。注意<math>S_k</math>的[[径宽]]为1，树深为2。

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

:<math>\varphi(T) \le \frac{5n}{\log_\Delta n}. </math>

更一般地说，对最大度不大于∆的[[平面图]]，类似约束也成立（参{{harvnb|Böttcher|Pruessmann|Taraz|Würfl|2010}}）：

:<math>\varphi(G) \le \frac{20n}{\log_\Delta n}.</math>

==计算带宽==
加与不加权的两类带宽计算问题都是[[二次瓶颈分配问题]]的特例。
带宽问题是[[NP困难]]的，即便对特例也如此。<ref>Garey–Johnson: GT40</ref>众所周知，带宽在任何常数范围内的近似都是NP难的，对最大毛长为2的[[毛虫树]]也如此{{harv|Dubey|Feige|Unger|2010}}。
对稠密图，{{harvtxt|Karpinski|Wirtgen|Zelikovsky|1997}}设计了一种3近似算法。
另一方面，我们也知道一些多项式可解的特例。<ref name=feige>"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}}</ref>[[Cuthill–McKee算法]]就是获得低带宽线图布局的[[启发法|启发式]]算法。图带宽计算的快速多层算法是在<ref name="multilevellinord">
{{cite journal
 | author = Ilya Safro and Dorit Ron and Achi Brandt
 | title = Multilevel Algorithms for Linear Ordering Problems
 | journal = ACM Journal of Experimental Algorithmics
 | year = 2008
 | pages = 1.4–1.20
 | volume = 13
 | doi=10.1145/1412228.1412232
 }}</ref>中提出的。

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

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

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

==另见==
*[[割宽]]与[[径宽]]

==参考文献==
{{reflist}}
*{{Cite journal | last1 = Böttcher | first1 = J. | last2 = Pruessmann | first2 = K. P. | last3 = Taraz | first3 = A. | last4 = Würfl | first4 = A. | title = Bandwidth, expansion, treewidth, separators and universality for bounded-degree graphs | doi = 10.1016/j.ejc.2009.10.010 | journal = European Journal of Combinatorics | volume = 31 | pages = 1217–1227 | year = 2010 | issue = 5 | arxiv = 0910.3014 }}
*{{Cite journal | last1 = Chinn | first1 = P. Z. |author1-link=Phyllis Chinn| last2 = Chvátalová | first2 = J. | last3 = Dewdney | first3 = A. K. |author3-link=Alexander Dewdney| last4 = Gibbs | first4 = N. E. | title = The bandwidth problem for graphs and matrices—a survey | url = https://archive.org/details/sim_journal-of-graph-theory_fall-1982_6_3/page/223 | journal = Journal of Graph Theory | volume = 6 | pages = 223–254| year = 1982 | issue = 3 | doi = 10.1002/jgt.3190060302 }}
*{{citation
 | last = Chung
 | first = Fan R. K.
 | author-link = Fan Chung
 | year = 1988
 | contribution = Labelings of Graphs
 | editor-last = Beineke
 | editor-first = Lowell W.
 | editor2-last = Wilson
 | editor2-first = Robin J.
 | title = Selected Topics in Graph Theory
 | publisher = Academic Press
 | pages = 151–168
 | isbn = 978-0-12-086203-0
 | url = http://www.math.ucsd.edu/~fan/mypaps/fanpap/86log.PDF
 | accessdate = 2024-01-31
 | archive-date = 2018-10-25
 | archive-url = https://web.archive.org/web/20181025015120/http://www.math.ucsd.edu/~fan/mypaps/fanpap/86log.PDF
 | dead-url = no
 }}
*{{Cite journal | last1 = Dubey | first1 = C. | last2 = Feige | first2 = U. | last3 = Unger | first3 = W. | title = Hardness results for approximating the bandwidth | journal = Journal of Computer and System Sciences | volume = 77 | pages = 62–90| year = 2010 | doi = 10.1016/j.jcss.2010.06.006 | doi-access = free }}
* {{cite book
 | last = Garey
 | first = M.R.
 | author-link = Michael Garey
 |author2=Johnson, D.S. |author-link2=David S. Johnson 
 | title = [[Computers and Intractability: A Guide to the Theory of NP-Completeness]]
 | year = 1979
 | publisher = W.H. Freeman
 | location = New York
 | isbn =  0-7167-1045-5
}}
*{{Citation
 | title = On Balanced Separators, Treewidth, and Cycle Rank
 | year = 2012
 | last = Gruber | first = Hermann
 | journal = Journal of Combinatorics
 | pages = 669–682
 | volume = 3
 | issue = 4
 | doi=10.4310/joc.2012.v3.n4.a5
| arxiv = 1012.1344
 }}
*{{Cite journal | last1 = Harper | first1 = L. | title = Optimal numberings and isoperimetric problems on graphs | journal = Journal of Combinatorial Theory | volume = 1 | pages = 385–393 | year = 1966 | issue = 3 | doi = 10.1016/S0021-9800(66)80059-5 | doi-access = free }}
*{{Citation
 | title = Pathwidth, bandwidth, and completion problems to proper interval graphs with small cliques
 | year = 1996
 | journal = [[SIAM Journal on Computing]]
 | pages = 540–561
 | volume = 25
 | issue = 3
 | last1 = Kaplan     | first1 =  Haim
 | last2 =  Shamir     | first2 =  Ron
 | doi=10.1137/s0097539793258143}}
*{{Cite journal | last1 = Karpinski | first1 = Marek | last2 = Wirtgen | first2 = Jürgen | last3 = Zelikovsky | first3 = Aleksandr | title = An Approximation Algorithm for the Bandwidth Problem on Dense Graphs | journal = Electronic Colloquium on Computational Complexity | volume = 4 | number = 17 | year = 1997 | url = http://eccc.hpi-web.de/report/1997/017/ | access-date = 2024-01-31 | archive-date = 2013-06-19 | archive-url = https://web.archive.org/web/20130619200022/http://eccc.hpi-web.de/report/1997/017/ | dead-url = no }}

==外部链接==
*[http://www.csc.kth.se/~viggo/wwwcompendium/node53.html Minimum bandwidth problem] {{Wayback|url=http://www.csc.kth.se/~viggo/wwwcompendium/node53.html |date=20221025090229 }}, in: Pierluigi Crescenzi and Viggo Kann (eds.), ''A compendium of NP optimization problems.'' Accessed May 26, 2010.

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