圖乘積

在圖論中，圖乘積為一個在圖上的二元運算，精確地說，這是一個需要兩個圖G₁和G₂，並產生出圖H 有著以下性質

關於用詞以及符號對於特定的圖乘積有非常多，讀者應當注意去確認作者使用的定義

圖表

以下的表格顯示了常見的圖乘積，並用 $\sim$ 記作兩頂點有被一條邊連接，用 $\nsim$ 記作兩頂點有未被一條邊連接

各種乘積	當 $(u_{1},u_{2})\sim (v_{1},v_{2})$ 的情況	頂點數與邊數 ${\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}}$
笛卡爾乘積(圖論) $G_{1}\square G_{2}$	( $u_{1}$ = $v_{1}$ and $u_{2}$ $\sim$ $v_{2}$ ) 或是 ( $u_{1}$ $\sim$ $v_{1}$ and $u_{2}$ = $v_{2}$ )	$m_{2}n_{1}+m_{1}n_{2}$
張量積(圖論) $G_{1}\times G_{2}$	$u_{1}$ $\sim$ $v_{1}$ and $u_{2}$ $\sim$ $v_{2}$	$2m_{1}m_{2}$
強乘積(AND乘積) $G_{1}\boxtimes G_{2}$	( u₁ = v₁ and u₂ ∼ v₂ ) 或是 ( u₁ ∼ v₁ and u₂ = v₂ ) 或是 ( u₁ ∼ v₁ and u₂ ∼ v₂ )	$n_{1}m_{2}+n_{2}m_{1}+2m_{1}m_{2}$
弱乘積(OR乘積) $G_{1}*G_{2}$	$(u_{1}\sim v_{1}{\text{ and }}u_{2}\sim v_{2})$ 或是 $(u_{1}\not \sim v_{1}{\text{ and }}u_{2}\not \sim v_{2})$
根乘積		$m_{2}n_{1}+m_{1}$

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.