图的张量积与积图运算
字数 3513 2025-12-19 17:11:18

图的张量积与积图运算

我们接下来详细讲解图的张量积（Tensor Product）以及更广泛的积图运算（Graph Products）。这是一个图论中通过已知图构造新图的重要方法，具有丰富的代数与组合性质。

1. 积图运算的基本概念与动机

积图运算是指将两个（或更多）给定的图 \(G\) 和 \(H\)，按照某种规则组合成一个新的图 \(G * H\)，其中 \(*\) 代表一种具体的乘积运算。常见的积图运算包括：

  • 笛卡尔积（Cartesian Product）
  • 张量积（Tensor Product，也称直积或Kronecker积）
  • 强积（Strong Product）
  • 字典积（Lexicographic Product）

这些运算在计算机科学（网络拓扑）、化学图论（分子结构）、代数图论（图的自同构群、谱理论）等领域有广泛应用。我们将重点放在张量积上，并与其他积进行对比以加深理解。

2. 张量积的正式定义

设 \(G = (V_1, E_1)\) 和 \(H = (V_2, E_2)\) 是两个无向简单图。它们的张量积（记作 \(G \times H\)）定义如下：

  • 顶点集：\(V(G \times H) = V_1 \times V_2\)，即所有有序对 \((u, v)\)，其中 \(u \in V_1\)， \(v \in V_2\)。
  • 边集：两个顶点 \((u_1, v_1)\) 和 \((u_2, v_2)\) 在 \(G \times H\) 中相邻，当且仅当 \(u_1 u_2 \in E_1\) 且 \(v_1 v_2 \in E_2\)。

换言之，新图中两个顶点相连的条件是：在第一个坐标上它们在 \(G\) 中相邻，同时在第二个坐标上它们在 \(H\) 中也相邻。这是一个“与”的逻辑条件。

3. 直观例子与图示

为了具体理解，我们考虑两个简单图：

  • \(G = P_2\)：一条2个顶点的路径（即一条边），设顶点为 \(a, b\)。
  • \(H = P_2\)：同样一条2个顶点的路径，设顶点为 \(x, y\)。

则 \(G \times H\) 的顶点为：\((a,x), (a,y), (b,x), (b,y)\)。

根据定义判断边：

  • \((a,x)\) 和 \((b,y)\) 是否相邻？在 \(G\) 中 \(a\) 和 \(b\) 相邻（是），在 \(H\) 中 \(x\) 和 \(y\) 相邻（是），所以 相邻。
  • \((a,x)\) 和 \((b,x)\) 是否相邻？在 \(G\) 中 \(a\) 和 \(b\) 相邻（是），但在 \(H\) 中 \(x\) 和 \(x\) 不是相邻的（同一个顶点，边要求两个不同顶点相邻），所以 不相邻。
  • \((a,x)\) 和 \((a,y)\) 是否相邻？在 \(G\) 中 \(a\) 和 \(a\) 不相邻，所以直接不符合条件。

最终，\(P_2 \times P_2\) 的边只有两条：\((a,x) \sim (b,y)\) 和 \((a,y) \sim (b,x)\)。这个图实际上是两个不相连的边（即 \(2K_2\)），它不连通，这与我们直觉中“乘积”可能保持连通性的想法不同，这是张量积的一个关键特性。

4. 张量积的基本性质

  1. 交换律：\(G \times H \cong H \times G\)（同构）。
  2. 结合律：\((G \times H) \times K \cong G \times (H \times K)\)。
  3. 单位元：单个顶点图 \(K_1\) 是张量积的单位元，即 \(G \times K_1 \cong K_1 \times G \cong G\)。
  4. 连通性：张量积的连通性条件较为苛刻。一个经典结论是：\(G \times H\) 是连通的当且仅当 \(G\) 和 \(H\) 都是连通的且至少有一个图不是二分图。如果两个图都是二分图，则张量积将不连通（通常有两个连通分支）。
  5. 度：顶点 \((u,v)\) 在 \(G \times H\) 中的度为 \(\deg_G(u) \cdot \deg_H(v)\)。
  6. 邻接矩阵：张量积的邻接矩阵是原图邻接矩阵的Kronecker积（张量积）：\(A(G \times H) = A(G) \otimes A(H)\)。这也正是其名称的来源。

5. 与其他积图运算的对比

为了更好地定位张量积，我们简要列出四种常见积的边定义规则（顶点集均为 \(V_1 \times V_2\)）：

  • 笛卡尔积 \(G \square H\): \((u_1, v_1) \sim (u_2, v_2)\) 当且仅当 （\(u_1 = u_2\) 且 \( v_1 v_2 \in E_2\)）或（\(v_1 = v_2\) 且 \( u_1 u_2 \in E_1\)）**。它像是沿着网格线移动。
  • 张量积 \(G \times H\): 如前所述，要求 \(u_1 u_2 \in E_1\) 且 \(v_1 v_2 \in E_2\)。
  • 强积 \(G \boxtimes H\): 边集是笛卡尔积和张量积边集的并集。即，只要满足两者之一的邻接条件即可。
  • 字典积 \(G \circ H\): \((u_1, v_1) \sim (u_2, v_2)\) 当且仅当 （\(u_1 u_2 \in E_1\)）或（\(u_1 = u_2\) 且 \(v_1 v_2 \in E_2\)）**。它赋予第一个坐标优先权。

这四种积中，张量积的邻接条件是最严格的，因此它的边通常最少，结构也更“稀疏”或“碎片化”。

6. 张量积的图论参数与复杂性

研究不同积图运算下图参数（如色数、团数、独立数、支配数等）的行为是一个重要课题。对于张量积，有一些著名而有趣的结论：

  • 色数 \(\chi\)：有赫德尼（Hedetniemi）猜想（1966年提出），它断言对于任意两个图 \(G\) 和 \(H\)，有 \(\chi(G \times H) = \min\{\chi(G), \chi(H)\}\)。这个猜想直观上意味着张量积的着色难度不超过因子图中较容易着色的那个。然而，该猜想在2019年被否定，莎拉·什拉利（Yaroslav Shitov）构造了反例，这是近年图论的一个重大进展。
  • 团数 \(\omega\)：容易证明 \(\omega(G \times H) = \omega(G) \cdot \omega(H)\)。因为张量积中的团对应于两个图中团的“完全配对”。
  • 独立数 \(\alpha\)：满足 \(\alpha(G \times H) \ge \alpha(G) \cdot \alpha(H)\)，但等式不一定成立。
  • 连通性：如前所述，条件苛刻。例如，\(C_4 \times K_2\)（两个四边形循环的张量积）是不连通的，因为 \(C_4\) 是二分图。

7. 应用与意义

  1. 网络建模：张量积可用于构建具有特定性质的网络拓扑，例如在并行计算中设计处理器连接网络。
  2. 图函数与同态：张量积与图同态（Homomorphism）理论紧密相连。图 \(G\) 到 \(H\) 的同态存在性等价于某种着色问题，而张量积在此框架下扮演了“乘积”的角色。
  3. 代数图论：其邻接矩阵的Kronecker积形式使得谱性质易于分析，特征值是原图特征值的乘积。
  4. 复杂性理论：赫德尼猜想的解决历程揭示了积图着色问题的深刻复杂性，推动了图同态和组合数学的前沿研究。

总结来说，图的张量积是一种通过严格的“双重邻接”条件组合两个图的方式，它虽然简单定义，却产生了丰富的、非平凡的结构性质，并与图论中多个核心领域（着色、连通性、同态、谱）深度交织。理解它有助于我们掌握更广泛的积图运算家族，并洞察图的结构如何通过运算进行组合与变换。

图的张量积与积图运算 我们接下来详细讲解图的张量积（Tensor Product）以及更广泛的积图运算（Graph Products）。这是一个图论中通过已知图构造新图的重要方法，具有丰富的代数与组合性质。 1. 积图运算的基本概念与动机 积图运算是指将两个（或更多）给定的图 \( G \) 和 \( H \)，按照某种规则组合成一个新的图 \( G * H \)，其中 \( * \) 代表一种具体的乘积运算。常见的积图运算包括： 笛卡尔积 （Cartesian Product） 张量积 （Tensor Product，也称直积或Kronecker积） 强积 （Strong Product） 字典积 （Lexicographic Product） 这些运算在计算机科学（网络拓扑）、化学图论（分子结构）、代数图论（图的自同构群、谱理论）等领域有广泛应用。我们将重点放在 张量积 上，并与其他积进行对比以加深理解。 2. 张量积的正式定义 设 \( G = (V_ 1, E_ 1) \) 和 \( H = (V_ 2, E_ 2) \) 是两个无向简单图。它们的 张量积 （记作 \( G \times H \)）定义如下： 顶点集 ：\( V(G \times H) = V_ 1 \times V_ 2 \)，即所有有序对 \((u, v)\)，其中 \( u \in V_ 1 \)， \( v \in V_ 2 \)。 边集 ：两个顶点 \((u_ 1, v_ 1)\) 和 \((u_ 2, v_ 2)\) 在 \( G \times H \) 中相邻，当且仅当 \( u_ 1 u_ 2 \in E_ 1 \) 且 \( v_ 1 v_ 2 \in E_ 2 \)。 换言之，新图中两个顶点相连的条件是：在第一个坐标上它们在 \( G \) 中相邻， 同时 在第二个坐标上它们在 \( H \) 中也相邻。这是一个“与”的逻辑条件。 3. 直观例子与图示 为了具体理解，我们考虑两个简单图： \( G = P_ 2 \)：一条2个顶点的路径（即一条边），设顶点为 \( a, b \)。 \( H = P_ 2 \)：同样一条2个顶点的路径，设顶点为 \( x, y \)。 则 \( G \times H \) 的顶点为：\((a,x), (a,y), (b,x), (b,y)\)。 根据定义判断边： \((a,x)\) 和 \((b,y)\) 是否相邻？在 \( G \) 中 \( a \) 和 \( b \) 相邻（是），在 \( H \) 中 \( x \) 和 \( y \) 相邻（是），所以 相邻 。 \((a,x)\) 和 \((b,x)\) 是否相邻？在 \( G \) 中 \( a \) 和 \( b \) 相邻（是），但在 \( H \) 中 \( x \) 和 \( x \) 不是相邻的（同一个顶点，边要求两个不同顶点相邻），所以 不相邻 。 \((a,x)\) 和 \((a,y)\) 是否相邻？在 \( G \) 中 \( a \) 和 \( a \) 不相邻，所以直接不符合条件。 最终，\( P_ 2 \times P_ 2 \) 的边只有两条：\((a,x) \sim (b,y)\) 和 \((a,y) \sim (b,x)\)。这个图实际上是两个不相连的边（即 \( 2K_ 2 \)），它 不连通 ，这与我们直觉中“乘积”可能保持连通性的想法不同，这是张量积的一个关键特性。 4. 张量积的基本性质 交换律 ：\( G \times H \cong H \times G \)（同构）。 结合律 ：\( (G \times H) \times K \cong G \times (H \times K) \)。 单位元 ：单个顶点图 \( K_ 1 \) 是张量积的单位元，即 \( G \times K_ 1 \cong K_ 1 \times G \cong G \)。 连通性 ：张量积的连通性条件较为苛刻。一个经典结论是：\( G \times H \) 是连通的当且仅当 \( G \) 和 \( H \) 都是连通的 且 至少有一个图不是二分图。如果两个图都是二分图，则张量积将不连通（通常有两个连通分支）。 度 ：顶点 \((u,v)\) 在 \( G \times H \) 中的度为 \( \deg_ G(u) \cdot \deg_ H(v) \)。 邻接矩阵 ：张量积的邻接矩阵是原图邻接矩阵的Kronecker积（张量积）：\( A(G \times H) = A(G) \otimes A(H) \)。这也正是其名称的来源。 5. 与其他积图运算的对比 为了更好地定位张量积，我们简要列出四种常见积的边定义规则（顶点集均为 \( V_ 1 \times V_ 2 \)）： 笛卡尔积 \( G \square H \) : \((u_ 1, v_ 1) \sim (u_ 2, v_ 2)\) 当且仅当 （ \( u_ 1 = u_ 2 \) 且 \( v_ 1 v_ 2 \in E_ 2\) ）或 （ \( v_ 1 = v_ 2 \) 且 \( u_ 1 u_ 2 \in E_ 1\) ）** 。它像是沿着网格线移动。 张量积 \( G \times H \) : 如前所述，要求 \( u_ 1 u_ 2 \in E_ 1 \) 且 \( v_ 1 v_ 2 \in E_ 2 \) 。 强积 \( G \boxtimes H \) : 边集是笛卡尔积和张量积边集的 并集 。即，只要满足两者之一的邻接条件即可。 字典积 \( G \circ H \) : \((u_ 1, v_ 1) \sim (u_ 2, v_ 2)\) 当且仅当 （ \( u_ 1 u_ 2 \in E_ 1 \) ）或 （ \( u_ 1 = u_ 2 \) 且 \( v_ 1 v_ 2 \in E_ 2 \) ）** 。它赋予第一个坐标优先权。 这四种积中， 张量积的邻接条件是最严格的 ，因此它的边通常最少，结构也更“稀疏”或“碎片化”。 6. 张量积的图论参数与复杂性 研究不同积图运算下图参数（如色数、团数、独立数、支配数等）的行为是一个重要课题。对于张量积，有一些著名而有趣的结论： 色数 \( \chi \) ：有赫德尼（Hedetniemi）猜想（1966年提出），它断言对于任意两个图 \( G \) 和 \( H \)，有 \( \chi(G \times H) = \min\{\chi(G), \chi(H)\} \)。这个猜想直观上意味着张量积的着色难度不超过因子图中较容易着色的那个。然而， 该猜想在2019年被否定 ，莎拉·什拉利（Yaroslav Shitov）构造了反例，这是近年图论的一个重大进展。 团数 \( \omega \) ：容易证明 \( \omega(G \times H) = \omega(G) \cdot \omega(H) \)。因为张量积中的团对应于两个图中团的“完全配对”。 独立数 \( \alpha \) ：满足 \( \alpha(G \times H) \ge \alpha(G) \cdot \alpha(H) \)，但等式不一定成立。 连通性 ：如前所述，条件苛刻。例如，\( C_ 4 \times K_ 2 \)（两个四边形循环的张量积）是不连通的，因为 \( C_ 4 \) 是二分图。 7. 应用与意义 网络建模 ：张量积可用于构建具有特定性质的网络拓扑，例如在并行计算中设计处理器连接网络。 图函数与同态 ：张量积与图同态（Homomorphism）理论紧密相连。图 \( G \) 到 \( H \) 的同态存在性等价于某种着色问题，而张量积在此框架下扮演了“乘积”的角色。 代数图论 ：其邻接矩阵的Kronecker积形式使得谱性质易于分析，特征值是原图特征值的乘积。 复杂性理论 ：赫德尼猜想的解决历程揭示了积图着色问题的深刻复杂性，推动了图同态和组合数学的前沿研究。 总结来说， 图的张量积 是一种通过严格的“双重邻接”条件组合两个图的方式，它虽然简单定义，却产生了丰富的、非平凡的结构性质，并与图论中多个核心领域（着色、连通性、同态、谱）深度交织。理解它有助于我们掌握更广泛的积图运算家族，并洞察图的结构如何通过运算进行组合与变换。