图乘积

在图论中，图乘积为一个在图上的二元运算，精确地说，这是一个需要两个图G₁和G₂，并产生出图H 有着以下性质

• 图H的顶点集合 是 笛卡尔乘积 V(G₁) × V(G₂)，其中 V(G₁)和 V(G₂)分别是图 G₁ 和 G₂的顶点集合。
• H的两个顶点(u₁, u₂)和(v₁, v₂) 是由一条边所连接顶点 u₁, u₂, v₁, v₂满足一个条件需要将图 G₁ 和 G₂的边列入考虑。

关于用词以及符号对于特定的图乘积有非常多，读者应当注意去确认作者使用的定义

图表

以下的表格显示了常见的图乘积，并用${\displaystyle \sim }$记作两顶点有被一条边连接，用${\displaystyle \nsim }$记作两顶点有未被一条边连接

各种乘积	当${\displaystyle (u_{1},u_{2})\sim (v_{1},v_{2})}$的情况	顶点数与边数 ${\displaystyle {\begin{array}{cc}n_{1}=\vert \mathrm {V} (G_{1})\vert &n_{2}=\vert \mathrm {V} (G_{2})\vert \\m_{1}=\vert \mathrm {E} (G_{1})\vert &m_{2}=\vert \mathrm {E} (G_{2})\vert \end{array}}}$	范例
笛卡尔乘积(图论)（英语：Cartesian product of graphs） ${\displaystyle G_{1}\square G_{2}}$	( ${\displaystyle u_{1}}$ = ${\displaystyle v_{1}}$ and ${\displaystyle u_{2}}$ ${\displaystyle \sim }$ ${\displaystyle v_{2}}$ ) 或是 ( ${\displaystyle u_{1}}$ ${\displaystyle \sim }$ ${\displaystyle v_{1}}$ and ${\displaystyle u_{2}}$ = ${\displaystyle v_{2}}$ )	${\displaystyle m_{2}n_{1}+m_{1}n_{2}}$
张量积(图论)（英语：Tensor product of graphs） ${\displaystyle G_{1}\times G_{2}}$	${\displaystyle u_{1}}$ ${\displaystyle \sim }$ ${\displaystyle v_{1}}$ and  ${\displaystyle u_{2}}$ ${\displaystyle \sim }$ ${\displaystyle v_{2}}$	${\displaystyle 2m_{1}m_{2}}$
强乘积(AND乘积) ${\displaystyle G_{1}\boxtimes G_{2}}$	( u1 = v1 and u2 ∼ v2 ) 或是 ( u1 ∼ v1 and u2 = v2 ) 或是 ( u1 ∼ v1 and u2 ∼ v2 )	${\displaystyle n_{1}m_{2}+n_{2}m_{1}+2m_{1}m_{2}}$
弱乘积(OR乘积) ${\displaystyle G_{1}*G_{2}}$	${\displaystyle (u_{1}\sim v_{1}{\text{ and }}u_{2}\sim v_{2})}$或是 ${\displaystyle (u_{1}\not \sim v_{1}{\text{ and }}u_{2}\not \sim v_{2})}$
根乘积		${\displaystyle m_{2}n_{1}+m_{1}}$

其他概念

• 图运算

参考