首页 > 代码库 > 子图同构

子图同构

子图同构定义:

      给定图$Q=(V(Q),E(Q),L_V,F)$和$G=(V(G),E(G),L_V‘,F‘)$,  称$Q$子图同构于$G$ 当且仅当存在一个映射$g:V(Q)\rightarrow V(G)$ 使得 

\[\forall x\in V(Q), F(v)=F‘(g(v))\]

\[
\forall v_1 ,v_2 \in V(Q),\overrightarrow {v_1 v_2 } \in E(Q) \Rightarrow \overrightarrow {g(v_1 )g(v_2 )} \in E(G)
\]

     例,左图子图同构与右图:

左图  Q                       右图  G

图 1

因为存在映射g(有两种),如下图所示:

   

左图  Q                            右图  G                                     左图  Q                           右图  G

图 2                                                                                   图 3

      用$MA,MB$分别表示图$Q,F$的对应的边矩阵,其中$MA[i][j]=1$表示顶点$v_i$与$v_j$有边,$MA[i][j]=0$表示无边. $M‘$表示映射g从$Q$到$G$的映射矩阵,$M‘[i][j]=1$表示$Q$中第$i$个顶点$v_i$对应到$G$中的第$j$个顶点$v_j^‘$,否则没有对应.

      例如,图2中的$Q,G,g$对应的矩阵可以表示为

                     

 

      定理  如果图$Q$关于映射$g$子图同构于$G$,令

\[
MC = M‘(M‘ \cdot MB)^T
\].

,则

\[
\forall i\forall j:(MA[i][j] = 1) \Rightarrow (MC[i][j] = 1).
\]

 

 

 

 

子图同构