主题
Search

图的笛卡尔积

DOWNLOAD Mathematica Notebook下载 Wolfram Notebook
GraphProduct

笛卡尔图积 G=G_1 square G_2，也称为图盒积，有时简称为“图”积（Beineke 和 Wilson 2004, p. 104），有时表示为 G_1×G_2（例如，Salazar 和 Ugalde 2004；尽管此符号更常用于不同的图张量积），对于具有不相交点集 V_1 和 V_2 以及边集 X_1 和 X_2 的图 G_1 和 G_2 而言，是点集为 V_1×V_2 的图，且 u=(u_1,u_2) 与 v=(v_1,v_2) 相邻当且仅当 [u_1=v_1 and u_2 adj v_2] 或 [u_2=v_2 and u_1 adj v_1] （Harary 1994, p. 22）。

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

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

其中 tensor 表示 克罗内克积（Hammack等人 2016）。

图的笛卡尔积可以使用 Wolfram 语言 计算，方法是GraphProduct[G1, G2,"Cartesian"].

如果 G 是单位距离图，那么 G square K_2 也是。更一般地，G 的图维度和 G square K_2 的图维度之间存在简单的关系（Erdős等人 1965, Buckley 和 Harary 1988）。

下表给出了一些图笛卡尔积的示例。这里，C_n 表示圈图，K_n 表示完全图，P_n 表示路径图，S_n 表示星图。

积结果
P_m square P_n网格图 G_(m,n)
P_m square P_2梯形图 L_m
P_l square P_m square P_n网格图 G_(l,m,n)
C_m square P_2棱柱图 Y_m
C_m square P_n堆叠棱柱图 Y_(m,n)
C_m square C_n环面网格图 T_(m,n)
C_m square C_n 其中 (m,n)=1循环图 Ci_(mn)(m,n)
S_(m+1) square P_2书图
S_(m+1) square P_n堆叠书图
K_2 square K_n^_皇冠图
K_n square C_rKC 图
K_n square P_rKP 图
K_m square K_nm×n 车图
K_m square K_n^_m×n 车补图
P_2 square ... square P_2_()_(n)超立方体图 Q_n

另请参阅

书图, 循环图, 皇冠图, 图的组合, 图的维度, 图的积, 网格图, KC 图, KP 图, 梯形图, 中值图, 棱柱图, 车补图, 车图, 堆叠书图, 环面网格图, 单位距离图, Vizing 猜想

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

使用 Wolfram|Alpha 探索

参考文献

Buckley, F. 和 Harary, F. "论轮的欧几里得维度。" Graphs and Combin. 4, 23-30, 1988.Beineke, L. W. 和 Wilson, R. J. (编). 代数图论主题。 纽约: Cambridge University Press, p. 104, 2004.Clark, W. E. 和 Suen, S. "与 Vizing 猜想相关的不等式。" Electronic J. Combinatorics 7, No. 1, N4, 1-3, 2000. http://www.combinatorics.org/Volume_7/Abstracts/v7i1n4.html.Erdős, P.; Harary, F.; 和 Tutte, W. T. "论图的维度。" Mathematika 12, 118-122, 1965.Hammack, R.; Imrich, W.; 和 Klavžar, S. 图积手册，第二版。 Boca Raton, FL: CRC Press, 2016.Harary, F. 图论。 Reading, MA: Addison-Wesley, 1994.Hartnell, B. 和 Rall, D. "笛卡尔积中的支配：Vizing 猜想。" 在 图的支配--高级主题 (编. T. W. Haynes, S. T. Hedetniemi, 和 P. J. Slater). 纽约: Dekker, pp. 163-189, 1998.Imrich, W. "Mengensystemen 和 Graphen 的 Kartesisches Produkt。" Studia Sci. Math. Hungar. 2, 285-290, 1967.Imrich, W.; Klavzar, S.; 和 Rall, D. F. 图及其笛卡尔积。 Wellesley, MA: A K Peters, 2008.Sabidussi, G. "图乘法。" Math. Z. 72, 446-457, 1960.Salazar, G. 和 Ugalde, E. "C_m×C_n 的交叉数的改进界限：主要使用组合论证的自包含证明。" Graphs Combin. 20, 247-253, 2004.Skiena, S. "图的积。" §4.1.4 在 实现离散数学：Mathematica 的组合学和图论。 Reading, MA: Addison-Wesley, pp. 133-135, 1990.Vizing, V. G. "图的笛卡尔积。" Vyčisl. Sistemy 9, 30-43, 1963.

在 Wolfram|Alpha 中被引用

图的笛卡尔积

请这样引用

Sauras-Altuzarra, Lorenzo 和 Weisstein, Eric W. "图的笛卡尔积。" 来自 MathWorld--Wolfram Web 资源。 https://mathworld.net.cn/GraphCartesianProduct.html

主题分类