图乘积

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

  • 图H的顶点集合 是 笛卡尔乘积 V(G1) × V(G2),其中 V(G1)和 V(G2)分别是图 G1G2的顶点集合。
  • H的两个顶点(u1u2)和(v1v2) 是由一条所连接顶点 u1, u2, v1, v2满足一个条件需要将图 G1G2的边列入考虑。

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

图表

以下的表格显示了常见的图乘积,并用 记作两顶点有被一条边连接,用 记作两顶点有未被一条边连接

各种乘积  的情况 顶点数与边数

 

范例
笛卡尔乘积(图论)英语Cartesian product of graphs

 

  =   and       )

或是

      and   =   )

   
张量积(图论)英语Tensor product of graphs

 

      and           
强乘积(AND乘积)

 

u1 = v1 and u2 ∼ v2 )

或是 ( u1 ∼ v1 and u2 = v2 )

或是 ( u1 ∼ v1 and u2 ∼ v2 )

 
弱乘积(OR乘积)

 

 或是

 

根乘积    

其他概念

参考