圖乘積

在圖論中，圖乘積為一個在圖上的二元運算，精確地說，這是一個需要兩個圖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}}$

其他概念

• 圖運算

參考