帶寬 (圖論)

圖論中，圖帶寬問題是用不同整數$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，其中超圖最小化了團大小。（Kaplan & Shamir 1996）

某些圖的帶寬公式

對部分圖族，帶寬$\varphi (G)$有明確公式給出。

n頂點上的路徑圖$P_{n}$的帶寬是1，對於完全圖$K_{m}$我們有$\varphi (K_{n})=n-1$。對完全二分圖$K_{m,\ n}$，有

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

由Chvátal證明。星圖$S_{k}=K_{k,1}$是此公式的特例，$k+1$個頂點上的星圖帶寬為$\varphi (S_{k})=\lfloor (k-1)/2\rfloor +1$。

$2^{n}$個頂點上的超立方圖$Q_{n}$的帶寬，Harper (1966)確定為

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

Chvatálová證明，$m\times n$方格圖$P_{m}\times P_{n}$（m、n個頂點上兩個路徑圖之笛卡爾積）的帶寬等於${\rm {min}}\{m,\ n\}$。

界

圖的帶寬可用各種圖參數約束。例如，令$\chi (G)$表示G的色數：

$\varphi (G)\geq \chi (G)-1;$

令${\rm {diam}}(G)$表示G的直徑，則有不等式：

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

其中n是G中頂點數。

k帶寬圖G的徑寬不大於k（Kaplan & Shamir 1996），其樹深不大於$k\log(n/k)$（Gruber 2012）。如上節所述，星圖$S_{k}$作為結構非常簡單的樹，帶寬相對較大。注意$S_{k}$的徑寬為1，樹深為2。

一些度有界圖族具有亞線性帶寬：Chung (1988)證明，若T是最大度不大於∆的樹，則

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

更一般地說，對最大度不大於∆的平面圖，類似約束也成立（參Böttcher et al. 2010）：

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

計算帶寬

加與不加權的兩類帶寬計算問題都是二次瓶頸分配問題的特例。 帶寬問題是NP困難的，即便對特例也如此。眾所周知，帶寬在任何常數範圍內的近似都是NP難的，對最大毛長為2的毛蟲樹也如此（Dubey，Feige & Unger 2010）。 對稠密圖，Karpinski，Wirtgen & Zelikovsky (1997)設計了一種3近似算法。 另一方面，我們也知道一些多項式可解的特例。Cuthill–McKee算法就是獲得低帶寬線圖布局的啟發式算法。圖帶寬計算的快速多層算法是在中提出的。

應用

對帶寬問題的興趣來自一些應用領域。

例如稀疏矩陣/帶狀矩陣處理與此領域的一般算法，如Cuthill–McKee算法，可用於尋找圖帶寬問題的近似解。

還有電子設計自動化。標準單元設計方法中，標準單元一般具有相同的高度，布局為若干行。這時，圖帶寬問題建模了將一組標準單元放置在單行中的問題，其目標是使最大傳播延遲（假定與導線長度成正比）最小化。

另見

• 割寬與徑寬

參考文獻

• 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, ISBN 978-0-12-086203-0 
• 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). 

外部連結

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