主题
Search

图的强积

DOWNLOAD Mathematica Notebook下载 Wolfram 笔记本

图的强积，也称为图的与积或图的正规积，是一种 图的积，有多种表示方法 G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H, G·H (Alon, and Lubetzky 2006), 或 G*H (Beineke and Wilson 2004, p. 104) ，由邻接关系 (g=g^' 且 hadjh^') 或 (gadjg^' 且 h=h^') 或 (gadjg^' 且 hadjh^') 定义。

换句话说，两个图 G_1 和 G_2 的图的强积具有 顶点集 V(G_1)×V(G_2)，并且两个不同的顶点 (v_1,v_2) 和 (u_1,u_2) 是连接的 当且仅当 它们在每个坐标中相邻或相等，即对于 i in {1,2}, 要么 v_i=u_i 要么 v_iu_i in E(G_i), 其中 E(G) 是 G 的 边集。

令 A(G) 表示 邻接矩阵，I_n 表示 n×n 单位矩阵，以及 |V(G)| 表示 G 的 顶点数，简单图 G 和 H 的图的强积的邻接矩阵由下式给出

A(G square H)=A(G) tensor I_(|V(H)|)+I_(|V(G)|) tensor A(H)+A(G) tensor A(H),

其中 tensor 表示 克罗内克积 (Hammack et al. 2016)。

图的强积可以使用 Wolfram 语言 计算，使用GraphProduct[G1, G2,"Normal"].

图的强积与称为 图的强度 的图论性质无关。

另请参阅

图的积, 图的强度, 香农容量

此条目部分内容由 Nicolas Bray 贡献

此条目部分内容由 Lorenzo Sauras-Altuzarra 贡献

使用 Wolfram|Alpha 探索

参考文献

Alon, N. and Lubetzky, E. "The Shannon Capacity of a Graph and the Independence Numbers of Its Powers." IEEE Trans. Inform. Th. 52, 2172-2176, 2006.Beineke, L. W. and Wilson, R. J. (Eds.). Topics in Algebraic Graph Theory. New York: Cambridge University Press, p. 104, 2004.Hammack, R.; Imrich, W.; and Klavžar, S. Handbook of Product Graphs, 2nd ed. Boca Raton, FL: CRC Press, 2016.

在 Wolfram|Alpha 中引用

图的强积

请引用为

Bray, Nicolas; Sauras-Altuzarra, Lorenzo; 和 Weisstein, Eric W. "Graph Strong Product." 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/GraphStrongProduct.html

主题分类