主题
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

另请参阅

带宽, 广播时间, 闲聊, 图扩张, 路径宽度, 树宽度

使用 Wolfram|Alpha 探索

参考文献

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. "图带宽。" 来自 MathWorld——Wolfram 网络资源。 https://mathworld.net.cn/GraphBandwidth.html

主题分类