图乘积此条目没有列出任何参考或来源。 (2020年3月23日)维基百科所有的内容都应该可供查证。请协助补充可靠来源以改善这篇条目。无法查证的内容可能会因为异议提出而移除。在图论中,图乘积为一个在图上的二元运算,精确地说,这是一个需要两个图G1和G2,并产生出图H 有着以下性质 图H的顶点集合 是 笛卡尔乘积 V(G1) × V(G2),其中 V(G1)和 V(G2)分别是图 G1 和 G2的顶点集合。 H的两个顶点(u1, u2)和(v1, v2) 是由一条边所连接顶点 u1, u2, v1, v2满足一个条件需要将图 G1 和 G2的边列入考虑。关于用词以及符号对于特定的图乘积有非常多,读者应当注意去确认作者使用的定义 图表 以下的表格显示了常见的图乘积,并用 ∼ {\displaystyle \sim } 记作两顶点有被一条边连接,用 ≁ {\displaystyle \nsim } 记作两顶点有未被一条边连接 各种乘积 当 ( u 1 , u 2 ) ∼ ( v 1 , v 2 ) {\displaystyle (u_{1},u_{2})\sim (v_{1},v_{2})} 的情况 顶点数与边数 n 1 = | V ( G 1 ) | n 2 = | V ( G 2 ) | m 1 = | E ( G 1 ) | m 2 = | E ( G 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) G 1 ◻ G 2 {\displaystyle G_{1}\square G_{2}} ( u 1 {\displaystyle u_{1}} = v 1 {\displaystyle v_{1}} and u 2 {\displaystyle u_{2}} ∼ {\displaystyle \sim } v 2 {\displaystyle v_{2}} ) 或是 ( u 1 {\displaystyle u_{1}} ∼ {\displaystyle \sim } v 1 {\displaystyle v_{1}} and u 2 {\displaystyle u_{2}} = v 2 {\displaystyle v_{2}} ) m 2 n 1 + m 1 n 2 {\displaystyle m_{2}n_{1}+m_{1}n_{2}} 张量积(图论)(英语:Tensor product of graphs) G 1 × G 2 {\displaystyle G_{1}\times G_{2}} u 1 {\displaystyle u_{1}} ∼ {\displaystyle \sim } v 1 {\displaystyle v_{1}} and u 2 {\displaystyle u_{2}} ∼ {\displaystyle \sim } v 2 {\displaystyle v_{2}} 2 m 1 m 2 {\displaystyle 2m_{1}m_{2}} 强乘积(AND乘积) G 1 ⊠ G 2 {\displaystyle G_{1}\boxtimes G_{2}} ( u1 = v1 and u2 ∼ v2 ) 或是 ( u1 ∼ v1 and u2 = v2 ) 或是 ( u1 ∼ v1 and u2 ∼ v2 ) n 1 m 2 + n 2 m 1 + 2 m 1 m 2 {\displaystyle n_{1}m_{2}+n_{2}m_{1}+2m_{1}m_{2}} 弱乘积(OR乘积) G 1 ∗ G 2 {\displaystyle G_{1}*G_{2}} ( u 1 ∼ v 1 and u 2 ∼ v 2 ) {\displaystyle (u_{1}\sim v_{1}{\text{ and }}u_{2}\sim v_{2})} 或是 ( u 1 ≁ v 1 and u 2 ≁ v 2 ) {\displaystyle (u_{1}\not \sim v_{1}{\text{ and }}u_{2}\not \sim v_{2})} 根乘积 m 2 n 1 + m 1 {\displaystyle m_{2}n_{1}+m_{1}} 其他概念 图运算参考