主題
Search

圖頻寬

DOWNLOAD Mathematica Notebook下載 Wolfram Notebook

連通圖 連通圖 G 的頻寬是在與 圖 G 同構的圖的所有可能的 鄰接矩陣 中，矩陣 頻寬 的最小值。等效地，它是圖編號的最小 圖擴張。頻寬有多種表示方法，記為 bw(G), B(G) 或 phi(G)。

單例圖 的頻寬未定義，但有時採用約定 bw(K_1)=0 或 bw(K_1)=1 (Miller 1988)。

非連通圖 的頻寬是其連通分量的頻寬的最大值。

連通圖 連通圖 G 的頻寬 bw(G) 滿足以下不等式

[(n-1)/(diam(G))]<=bw(G)<=n-diam(G)

(Chinn等人 1982)，其中 n=|G| 是 G 的 頂點數，而 G 是 圖直徑，且

bw(G)>=chi(G)-1,

其中 chi(G) 是 色數。

計算圖的頻寬是 NP 困難的。

Harper (1964) 考慮了圖頻寬的界限，k-立方體的頻寬由 Harper (Harper 1966, Wang 和 Wu 2007, Harper 2010) 確定。

特殊情況總結在下表中。

圖頻寬
反稜柱圖4
雞尾酒會圖 K_(n×2)2(n-1)
完全二部圖 K_(m,n)|_1/2[max(m,n)-1]_|+min(m,n)
完全圖 K_nn-1
圈圖 C_n2
網格圖 P_m square P_nmin(m,n)
超立方體圖 Q_nsum_(k=0)^(n-1)(k; |_k/2_|)
莫比烏斯梯子圖 M_n4
平底鍋圖2
路徑圖 P_n1
稜柱圖4
星圖 S_n|_n/2_|
太陽圖n-1
三角網格圖 T_nn+1
輪圖 W_n{3 for n<=5; |_n/2_| for n>=6

另請參閱

頻寬, 廣播時間, 閒聊, 圖擴張, 路徑寬度, 樹寬度

使用 探索

參考文獻

Böttcher, J.; Preussmann, K. P.; Taraz, A.; 和 Würfl, A. "頻寬、擴張、樹寬度、分隔符和有界度圖的普遍性。" Eur. J. Combin. 31, 1217-1227, 2010.Chinn, P. Z.; Chvátalová, J.; Dewdney, A. K.; 和 Gibbs, N. E. "圖和矩陣的頻寬問題——綜述。" J. Graph Th. 6, 223-254, 1982.Chvátalová, J. "兩條路徑乘積的最優標記。" Disc. Math. 11, 249-253, 1975.Harper, L. H. "數字到頂點的最優分配。" J. Soc. Indust. Appl. Math. 12, 131-135, 1964.Harper, L. H. "圖上的最優編號和等周問題。" J. Combin. Th. 1, 385-393, 1966.Harper, L. H. 組合等周問題的全域性方法。 Cambridge, England: Cambridge University Press, 2010.Miller, Z. "用於度為三的樹的拓撲頻寬的線性演算法。" SIAM J. Comput. 17, 1018-1035, 1988.Wang, X. 和 Wu, X. "Hales 編號超立方體的遞迴結構和頻寬。" 2007 年 8 月 27 日。 http://arxiv.org/abs/0708.3628.West, D. B. 圖論導論，第二版。 Englewood Cliffs, NJ: Prentice-Hall, p. 390, 2000.

請引用本文為

Weisstein, Eric W. "圖頻寬。" 來自 ——Wolfram 網路資源。 https://mathworld.tw/GraphBandwidth.html

主題分類