子图同构问题

子图同构（Subgraph Isomorphism）是指在图论中，两个图之间是否存在一种关系，使得其中一个图的顶点集合和边集合可以通过对应的方式映射到另一个图的顶点集合和边集合上，且保持原来的边和顶点的关系不变。

具体来说，给定两个图$G=(V_G,E_G)$和$H=(V_H,E_H)$，若存在一种从$G$到$H$的映射$\varphi :V_G\to V_H$，满足：

对于$V_G$中的任意两个不同的顶点$v_i$和$v_j$，如果在$E_G$中有边连接它们，那么在$E_H$中$\varphi (v_i)$和$\varphi (v_j)$也必须有一条边连接；

对于$V_H$中的任意两个不同的顶点$v_i^{\prime }$和$v_j^{\prime }$，如果在$E_H$中有边连接它们，那么在$E_G$中存在$v_i$和$v_j$，满足$\varphi (v_i)=v_i^{\prime }$，$\varphi (v_j)=v_j^{\prime }$，且在$E_G$中也有边连接$v_i$和$v_j$。

如果这样的映射$\varphi$存在，则称图$G$是图$H$的子图，并称$\varphi$为从$G$到$H$的子图同构映射。

---

这左图与右图子图同构

存在如下映射关系：

用$MA,MB$分别表示左图A,和右图B的对应的邻接矩阵，其中$MA[i][j]=1$表示顶点$i$与$j$存在一条边, $MA[i][j]=0$表示无边

$M^{\prime }$表示映射从$MA$到$MB$的映射矩阵，$M[i][j]=1$表示A中第$i$个顶点$vi$对应到$MB$中的第$j$个顶点,否则为$0$表示没有对应

---

上图是一个图同构的例子，顶点之间并没有颜色区分，为了更好地看出顶点间的映射关系，加上了颜色。

子图同构在图形识别、化学结构分析、计算机视觉、网络安全等领域都有广泛应用。但是在实际问题中，子图同构问题往往是 NP 难问题，因此需要采用各种方法进行求解。

单射函数和双射函数

单射函数和双射函数都是函数的特殊类型。

单射函数（injective function），也称为一对一函数，是指一个函数f：A→B，其中任意一个B中的元素b，都最多只对应一个A中的元素a，即对于任意的b∈B，都有至多一个a∈A，使得f(a)=b。

双射函数（bijective function），也称为一一对应函数，是指一个函数f：A→B，其中A和B是两个集合，满足下面两个条件：

对于任意的$a\in A$，都存在一个$b\in B$，使得$f(a)=b$。
对于任意的$b\in B$，都存在一个$a\in A$，使得$f(a)=b$。

换言之，双射函数是一种既是单射函数又是满射函数的函数。

区别在于，单射函数保证了每个B中的元素最多只对应一个A中的元素，但不保证每个B中的元素都有对应的A中的元素；而双射函数则保证了每个B中的元素都有对应的A中的元素，并且每个B中的元素最多只对应一个A中的元素。

同构（isomorphic）和同态（homomorphism）

简单来讲，对于两个不带标签的无向图，假设$G1=(E1,V1),G2=(E2,V2)$，如果存在一种映射关系$M$ ，使得$M(v1)\in G2,(M(v1),M(v1\prime ))\in G2$，对于每个$v1,v1\prime \in G1$，那么图同态；若$M$是一个单射函数，则$G1,G2$同构。该定义可以扩充到其他更复杂类型的图中。

因此，同构必定是同态的。

对于上面的图，是一个同态图但是不是同构图。

因为存在这样一个映射函数f满足：$f(a)=x,f(b)=y,f(c)=z,f(d)=x,f(e)=y$。显然映射函数f不是单射函数，所以这两个图同态但不同构。