主题
Search

图乘积

一般来说，两个图 G 和 H 的图乘积是一个新图，其顶点集为 V(G)×V(H)，其中，对于乘积中的任意两个顶点 (g,h) 和 (g^',h^')，这两个顶点的邻接性完全由 g 和 g^' 的邻接性（或相等性，或非邻接性）以及 h 和 h^' 的邻接性决定。有 3×3-1=8 种情况需要决定（每个有三种可能性，其中两者相等的情况被排除），因此可以定义 2^8=256 种不同类型的图乘积。

最常用的图乘积，由邻接的充分必要条件给出，总结在下表中（Hartnell 和 Rall 1998）。请注意，术语并非完全标准化，因此这些乘积实际上可能被不同来源以不同的名称提及（例如，图字典序乘积也称为图组合；Harary 1994，第 21 页）。在 Jensen 和 Toft (1994) 中可以找到许多其他图乘积；另请参见 Hammack 等人 (2016)。

图乘积可以使用 Wolfram 语言计算，使用GraphProduct[G, H, type]，其中术语"Normal"用于图强乘积。

图乘积名称符号定义
图笛卡尔积G square H(g=g^' 且 hadjh^') 或 (gadjg^' 且 h=h^'>)</td></tr><tr style=图字典序积G-H(gadjg^') 或 (g=g^' 且 hadjh^'>)</td></tr><tr style=图强积G□AdjustmentBox[x, BoxMargins -> {{-0.65, 0.13913}, {-0.5, 0.5}}, BoxBaselineShift -> -0.1]H(g=g^' 且 hadjh^') 或 (gadjg^' 且 h=h^') 或 (gadjg^' 且 hadjh^'>)</td></tr><tr style=图张量积G×H(gadjg^' 且 hadjh^'>)</td></tr> </tbody></table> </div> </div> <!-- End Content --> <hr class=

另请参阅

图笛卡尔积, 图张量积, 图组合, 图日冕积, 图字典序积, 图幂, 图强积, 图和

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

使用 Wolfram|Alpha 探索

参考文献

Hammack, R.; Imrich, W.; 和 Klavžar, S. 图乘积手册，第二版。 Boca Raton, FL: CRC Press, 2016.Harary, F. 图论。 Reading, MA: Addison-Wesley, 1994.Hartnell, B. 和 Rall, D. "笛卡尔积中的支配：维辛猜想。" 在 图的支配--高级主题 (Ed. T. W. Haynes, S. T. Hedetniemi, 和 P. J. Slater). New York: Dekker, pp. 163-189, 1998.Imrich, W. 和 Klavžar, S. 图乘积：结构与识别。 New York: Wiley, 2000.Imrich, W.; KlavĽorezar, S.; 和 Rall, D. F. 图及其笛卡尔积。 Wellesley, MA: A K Peters, 2008.Jensen, T. R. 和 Toft, B. 图着色问题。 New York: Wiley, 1994.

在 Wolfram|Alpha 中被引用

图乘积

请引用为

布雷，尼古拉斯 和 韦斯坦因，埃里克·W. "图乘积。" 来自 MathWorld——Wolfram Web 资源。 https://mathworld.net.cn/GraphProduct.html

主题分类