圖論中,圖帶寬問題是用不同整數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. 

外部連結

編輯