主题
Search

图强度

下载 Mathematica 笔记本下载 Wolfram 笔记本

关于图的强度有几种定义。

Harary 和 Palmer（1959）以及 Harary 和 Palmer（1973，p. 66）将树的强度定义为任意顶点对之间边的最大数量。此定义对应于树的图直径。

Harary 和 Palmer（1973，p. 117）将多重图的强度定义为连接任意两个相邻顶点的边的最大数量。

GraphStrengthCapobiancoMolluzzo

Capobianco 和 Molluzzo（1979-1980）将可分图的强度定义为 1/S.S，其中图的强度向量 S 定义为向量 {s_i}，其中 s_i 是删除顶点 i 后连通分量计数的增加量。例如，上面图示的图的 Capobianco-Molluzzo 强度向量为 {-1,0,0,0,0,2,1,1,0}。不可分图的 Capobianco-Molluzzo 强度然后被定义为 infty。

简单连通图 G 的强度的最标准定义 sigma(G) 是

sigma(G)=min_(S)(|S|)/(c(G-S)-1),

其中 c 是连通分量的数量，最小值取自 G 的所有边割 S (Gusfield 1983, 1991)。在这里，分母中减一给出了创建的额外连通分量的数量。因此，图强度衡量了图对边删除的抵抗力，因此是对网络遭受攻击的脆弱性的度量（Cunningham 1985，Gusfield 1991），并且可以自然地推广到边加权图。图强度的计算可以在多项式时间内完成（Cunningham 1985，Trubin 1993）。

虽然人们可以将 sigma(G)=0 用于不连通图，如 Chvátal (1973) 在图韧性的类似情况中所做的那样，但应用边割的定义作为增加连通分量数量的割，可以为不连通图提供明确定义的强度。

顶点割 图强度的类似物被称为图韧性。

Tutte-Nash-Williams 定理指出 |_sigma(G)_|，其中 |_x_| 是向下取整函数，是可以包含在图 G 中的边不相交生成树的最大数量 (Gusfield 1984, Cunningham 1985)。

图强度与图强积无关。

另请参阅

图直径、图距离矩阵、图强积、图韧性

使用 Wolfram|Alpha 探索

参考文献

Capobianco, M. C. 和 Molluzzo, J. C. "图的强度及其在组织结构中的应用。" Social Networks 2, 275-283, 1979-1980。Chvátal, V. "强韧图和哈密顿回路。" Disc. Math. 5, 215-228, 1973。Cunningham, W. H. "网络的最佳攻击和加强。" J. Assoc. Comput. Mach. 32, 549-561, 1985。Gusfield, D. "连通性和边不相交生成树。" Inf. Proc. Lett. 16, 97-99, 1983。Gusfield, D. "计算图的强度。" SIAM J. Comput. 20, 639-654, 1991。Harary, F. 和 Prins, G. "同胚不可约树的数量和其他种类。" Acta Math. 101, 141-162, 1959。Harary, F. 和 Palmer, E. M. 图的计数。 纽约：学术出版社，pp. 66 和 117, 1973。Nash-Williams, C. St. J. A. "有限图的边不相交生成树。" J. London Math. Soc. 36, 445-450, 1961。Schrijver, A. 组合优化：多面体和效率，卷 B。 柏林：施普林格出版社，pp. 878 和 891, 2003。Trubin, V. A. "图的强度以及树和分支的打包。" Cyber. Syst. Anal. 29, 379-384, 1993。Tutte, W. T. "将图分解为连通因子的难题。" J. London Math. Soc. 36, 221-230, 1961。

引用为

Weisstein, Eric W. "图强度。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/GraphStrength.html

主题分类