查看“︁圖乘積”︁的源代码

{{Unreferenced|time=2020-03-23T06:50:53+00:00}}
在[[圖論]]中，圖乘積為一個在圖上的二元運算，精確地說，這是一個需要兩個圖G<sub>1</sub>和G<sub>2</sub>，並產生出圖H 有著以下性質

* 圖H的頂點集合 是 笛卡爾乘積 ''V''(''G''<sub>1</sub>)&nbsp;&#xD7;&nbsp;''V''(''G''<sub>2</sub>)，其中 ''V''(''G''<sub>1</sub>)和 ''V''(''G''<sub>2</sub>)分別是圖 ''G''<sub>1</sub> 和 ''G''<sub>2</sub>的頂點集合。
* H的兩個頂點(''u''<sub>1</sub>,&nbsp;''u''<sub>2</sub>)和(''v''<sub>1</sub>,&nbsp;''v''<sub>2</sub>) 是由一條[[邊 (圖論)|邊]]所連接頂點 ''u''<sub>1</sub>, ''u''<sub>2</sub>, ''v''<sub>1</sub>, ''v''<sub>2</sub>滿足一個條件需要將圖 ''G''<sub>1</sub> 和 ''G''<sub>2</sub>的邊列入考慮。

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

== 圖表 ==
以下的表格顯示了常見的圖乘積，並用<math>\sim</math>記作兩頂點有被一條邊連接，用<math>\nsim</math>記作兩頂點有未被一條邊連接
{| class="wikitable"
!各種乘積
!當<math>(u_{1},u_{2})\sim(v_{1},v_{2})</math>的情況
!頂點數與邊數
<math>\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}</math>
!範例
|-
|{{link-en|笛卡爾乘積(圖論)|Cartesian product of graphs}}
<math>G_1 \square G_2</math>
|(&nbsp;<math>u_1</math>&nbsp;=&nbsp;<math>v_1</math>&nbsp;and&nbsp;<math>u_2</math>&nbsp;<math>\sim</math>&nbsp;<math>v_2</math>&nbsp;)
或是

(&nbsp;<math>u_1</math>&nbsp;<math>\sim</math>&nbsp;<math>v_1</math>&nbsp;and&nbsp;<math>u_2</math>&nbsp;=&nbsp;<math>v_2</math>&nbsp;)
|<math>m_2 n_1 + m_1 n_2</math>
|[[File:Graph-Cartesian-product.svg|200x200像素]]
|-
|{{link-en|張量積(圖論)|Tensor product of graphs}}
<math>G_1 \times G_2</math>
|<math>u_1</math>&nbsp;<math>\sim</math>&nbsp;<math>v_1</math>&nbsp;and &nbsp;<math>u_2</math>&nbsp;<math>\sim</math>&nbsp;<math>v_2</math>
|<math>2 m_1 m_2</math>
|[[File:Graph-tensor-product.svg|200x200像素]]
|-
|強乘積(AND乘積)
<math>G_1 \boxtimes G_2</math>
|(&nbsp;''u''<sub>1</sub>&nbsp;=&nbsp;''v''<sub>1</sub>&nbsp;and&nbsp;''u''<sub>2</sub>&nbsp;&#x223C;&nbsp;''v''<sub>2</sub>&nbsp;)
或是
(&nbsp;''u''<sub>1</sub>&nbsp;&#x223C;&nbsp;''v''<sub>1</sub>&nbsp;and&nbsp;''u''<sub>2</sub>&nbsp;=&nbsp;''v''<sub>2</sub>&nbsp;)

或是
(&nbsp;''u''<sub>1</sub>&nbsp;&#x223C;&nbsp;''v''<sub>1</sub>&nbsp;and&nbsp;''u''<sub>2</sub>&nbsp;&#x223C;&nbsp;''v''<sub>2</sub>&nbsp;)
|<math>n_1 m_2 + n_2 m_1 + 2 m_1 m_2</math>
|
|-
|弱乘積(OR乘積)
<math>G_1 * G_2</math>
|<math>(u_1 \sim v_1 \text{ and } u_2 \sim v_2)</math>或是
<math>(u_1 \not\sim v_1 \text{ and } u_2 \not\sim v_2)</math>
|
|
|-
|根乘積
|
|<math>m_2 n_1 + m_1</math>
|[[File:Graph-rooted-product.svg|200x200像素]]
|}

== 其他概念 ==

* [[圖運算]]

== 參考 ==
<br />

{{图论}}

[[Category:图论]]