图的张量积与积图 我们先从图的基本运算开始理解。两个图 G 和 H 的 张量积 （也称为直积或Kronecker积），记作 G × H，其顶点集是 G 和 H 顶点集的笛卡尔积 V(G) × V(H)。对于两个顶点 (u, v) 和 (u', v')，它们在 G × H 中相邻当且仅当在 G 中 u 与 u' 相邻，并且在 H 中 v 与 v' 相邻。这是一个纯粹的“且”关系。 接下来，我们对比其他常见的积图运算。 笛卡尔积 G □ H 的顶点集同样是 V(G) × V(H)，但其邻接关系定义为：要么 u = u' 且 v 与 v' 在 H 中相邻，要么 v = v' 且 u 与 u' 在 G 中相邻。这是一个“或”关系。而 强积 G ⊠ H 的边集是张量积和笛卡尔积边集的并集，即邻接关系最丰富的一种积。 张量积的一个关键性质是其在 图同态 中的核心地位。图 G 到图 H 存在一个同态，当且仅当在张量积 G × H 的补图中，存在一个与 G 同构的子图。这建立了图染色理论与积图之间的深刻联系。例如，图 G 的色数 χ(G) 可以定义为满足 G 到完全图 K_ n 存在同态的最小整数 n。利用张量积，著名的 Hedetniemi猜想 （现已被否定）曾猜想 χ(G × H) = min{χ(G), χ(H)}，但Shitov在2019年给出了反例。 张量积的连通性也很有趣。即使 G 和 H 都是连通的，它们的张量积 G × H 也可能是不连通的。其连通分量个数与 G 和 H 的因子在某种等价关系下的类数有关。此外，张量积的 邻接矩阵 恰好是原图邻接矩阵的Kronecker张量积，这使得它在代数图论和量子图论中具有重要应用。 最后，我们探讨其在 并行计算 中的意义。张量积图可以自然地模拟多处理器系统间的通信网络，其中每个处理器由一对坐标标识，通信发生在两个坐标都同时变化时。这种网络拓扑结构的研究有助于分析并行算法的效率。