子图同构定义：
给定图$Q=(V(Q),E(Q),L_V,F)$和$G=(V(G),E(G),L_V',F')$, 称$Q$子图同构于$G$ 当且仅当存在一个映射$g:V(Q) ightarrow V(G)$ 使得
[forall xin 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$对应的矩阵可以表示为
图 4
定理 1 如果图$Q$关于映射$g$子图同构于$G$，令
[
MC = M'(M' cdot MB)^T
].
，则
[
forall iforall j:(MA[i][j] = 1) Rightarrow (MC[i][j] = 1).
]
根据图4，$MC = M'(M' cdot MB)^T $，由于
这里显然，$MA$与$MC$满足定理1.
子图同构映射$g$的$M’$满足一下性质：
- $M'[i][j]=1$ 表示Q中第$i$-个顶点对应$G$中的第$j$个顶点；
- $M'$的每行仅有一个$1$;
- $M'$的每列$1$的个数至多只有一个。
子图同构就变成了寻找矩阵$M'$，那么如何寻找$M'$？1976年Ullmann给出了寻找算法（Ullmann Algorithm）.
Ullmann Algorithm的大致过程：
- 寻找矩阵$M'_{n imes m}$使得[MC = M'(M' cdot MB)^T , forall iforall j:(MA[i][j] = 1) Rightarrow (MC[i][j] = 1).]
- 否则，报告不存在矩阵$M'$.
Ullmann Algorithm的基本思想：
Step 1. 建立矩阵$M_{n imes m}$。 使得$M[i][j]=1$，如果
- Q中第$i$-个顶点与$G$中第$j$-个顶点有相同的标签；
- Q中第$i$-个顶点的度小于等于$G$中第$j$-个顶点的度；
Step 2. 从矩阵$M_{n imes m}$生成矩阵$M'$. 即对$M_{n imes m}$进行逐行检查，将部分不为0的元素变成0，使得矩阵$M'$满足每行有且仅有一个元素为1,每列最多只有一个元素不为0.（最大深度为$|MA|$.）
Step 3 按照以下规则判断矩阵$M'$是否满足条件：
[MC = M'(M' cdot MB)^T , forall iforall j:(MA[i][j] = 1) Rightarrow (MC[i][j] = 1).]
Step 4 迭代以上步骤，列出所有可能的矩阵$M'$.
以上最坏的情况是，可能有$O(|MB|!)$个可能的矩阵$M'$. 实际上，子图同构算法是一个经典的NP-hard问题。