子图同构算法Ullmann早在1976年就提出来了，大家有兴趣可以自己去搜索下原文看看。这里我就简要的阐述一下。

给定两个图Q 和 G, 它们相应的矩阵分别是和.我们的目标就是找到矩阵

算法步骤：

       Step1. Setup matrix M_n×m , such that M[i][j]=1, if 1) the i-th vertex in Q hasthe same label as the j-th vertex in G; and 2) the i-th vertex has smallervertex degree than the j-th vertex in G.

       Step2.MatrixesM are generated by systematically changing to 0 all but one of the 1’s in eachof the rows of M, subject to the definitory condition that no column of amatrix M may contain more than one 1. 

       Step3.Verify matrix M’ by the following equation

为了提高算法的效率，采用了如下的Refinement。

Refinement:

Letthe i-th vertex v in Q corresponds to the j-th vertex u in G.Each neighbor vertex ofv in Q must correspond to some neighbor vertexof u in G.  Otherwise,vcannot correspond to u.

 1. Considering the matrix M, for each 1 in M, we refine it by the followingequation. If fails, change 1 to 0 in M.

 2.  If there exists at least one row (in M) having no 1, we report no subgraphisomorphism from Q to G.

接下来就直接粘贴代码了。

package ucas.iie.graph.action;

import java.io.BufferedReader;
import java.io.FileInputStream;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;

import ucas.iie.graph.bean.EdgeBean;
import ucas.iie.graph.bean.GraphBean;
import ucas.iie.graph.bean.VertexBean;

public class IsomorphismImpl {
	private ArrayList<GraphBean> query_g;// 查询的子图
	private ArrayList<GraphBean> mydb_g;// 图的总数据

	public IsomorphismImpl() {
		query_g = new ArrayList<GraphBean>();
		mydb_g = new ArrayList<GraphBean>();
	}

	/**
	 * 
	 * @param query
	 * @param db
	 * @return 返回初始的矩阵M0
	 */
	public int[][] getMatrixM(GraphBean query, GraphBean db) {
		int row = query.getvList().size();
		int column = db.getvList().size();
		int[][] M0 = new int[row][column];
		// System.out.println("M0:");
		for (int i = 0; i < row; i++) {
			for (int j = 0; j < column; j++) {
				String vi = query.getvList().get(i).getVertex();
				String vj = db.getvList().get(j).getVertex();
				if (db.getVDegree(vj) >= query.getVDegree(vi))
					M0[i][j] = 1;
				else
					M0[i][j] = 0;
				// System.out.print(M0[i][j] + " ");
			}
			// System.out.println("");
		}
		return M0;
	}

	public ArrayList<GraphBean> getQuery_g() {
		return query_g;
	}

	public void setQuery_g(ArrayList<GraphBean> query_g) {
		this.query_g = query_g;
	}

	public ArrayList<GraphBean> getMydb_g() {
		return mydb_g;
	}

	public void setMydb_g(ArrayList<GraphBean> mydb_g) {
		this.mydb_g = mydb_g;
	}

	/**
	 * 
	 * @param queryFile
	 *            查询子图的路径
	 * @param dbFile
	 *            图的总数据路径
	 * @throws IOException
	 */
	public void initGraphDB(String queryFile, String dbFile) throws IOException {
		// 读取查询子图的数据
		BufferedReader q_br = new BufferedReader(new InputStreamReader(
				new FileInputStream(queryFile)));
		String lineData = http://www.mamicode.com/q_br.readLine();>
package ucas.iie.graph.bean;

import java.util.ArrayList;

public class GraphBean {
	/** 图的数据格式
	 *  t # 0 表示第0个图
		v 0 2
		v 1 2
		v 2 2
		v 3 2
		v 4 2
		e 0 1 2
		e 1 2 2
		e 2 3 2
		e 3 4 2
	 */
	private ArrayList<VertexBean> vList;
	private ArrayList<EdgeBean> eList;
	public GraphBean(){
		vList = new ArrayList<VertexBean>();
		eList = new ArrayList<EdgeBean>();
	}
	public ArrayList<VertexBean> getvList() {
		return vList;
	}
	public void setvList(ArrayList<VertexBean> vList) {
		this.vList = vList;
	}
	public ArrayList<EdgeBean> geteList() {
		return eList;
	}
	public void seteList(ArrayList<EdgeBean> eList) {
		this.eList = eList;
	}	
	public int[][] getMatrix(){
		int[][] M = new int[vList.size()][vList.size()];
		for (int index = 0; index < eList.size(); index++) {
			EdgeBean eb = eList.get(index);
			int i = Integer.parseInt(eb.getVertex_i());
			int j = Integer.parseInt(eb.getVertex_j());
			M[i][j] = 1;
			M[j][i] = 1;
		}
//		System.out.println("MA/MB:");
//		for (int i = 0; i < vList.size(); i++) {
//			for (int j = 0; j < vList.size(); j++) {
//				System.out.print(M[i][j] + " ");
//			}
//			System.out.println();
//		}
		return M;
	}
	/**
	 * 
	 * @param v
	 * @return 返回顶点v的度
	 */
	public int getVDegree(String v){
		int sumDeg = 0;
		for (int i = 0; i < eList.size(); i++) {
			if(eList.get(i).getVertex_i().equals(v)||
					eList.get(i).getVertex_j().equals(v)){
				sumDeg ++;
			}
		}
		return sumDeg;
	}
	public String toString(){
		String res = "";
		for (int i = 0; i < this.vList.size(); i++) {
			res +="v " + vList.get(i).getVertex()  + " " + vList.get(i).getLabel() + "\r\n";
		}
		for (int j = 0; j < this.eList.size(); j++) {
			res +="e " + eList.get(j).getVertex_i()  + " " + eList.get(j).getVertex_j() + " "+eList.get(j).getLabel_e() + "\r\n";
		}
		return res;
	}
	public static void main(String[] args) {
		new GraphBean().getMatrix();
	}
}

package ucas.iie.graph.bean;

public class EdgeBean {//“e i j k” 表示图的边<i,j>的label是k 
	/** 图的数据格式
	 *  t # 0 表示第0个图
		v 0 2
		v 1 2
		v 2 2
		v 3 2
		v 4 2
		e 0 1 2
		e 1 2 2
		e 2 3 2
		e 3 4 2
	 */
	private String vertex_i;
	private String vertex_j;
	private String label_e;
	public String getVertex_i() {
		return vertex_i;
	}
	public void setVertex_i(String vertex_i) {
		this.vertex_i = vertex_i;
	}
	public String getVertex_j() {
		return vertex_j;
	}
	public void setVertex_j(String vertex_j) {
		this.vertex_j = vertex_j;
	}
	public String getLabel_e() {
		return label_e;
	}
	public void setLabel_e(String label_e) {
		this.label_e = label_e;
	}
}

package ucas.iie.graph.bean;
public class VertexBean { //“v i j” 表示图的顶点i的label是j 
	/** 图的数据格式
	 *  t # 0 表示第0个图
		v 0 2
		v 1 2
		v 2 2
		v 3 2
		v 4 2
		e 0 1 2
		e 1 2 2
		e 2 3 2
		e 3 4 2
	 */
	private String vertex;
	private String label;
	public String getVertex() {
		return vertex;
	}
	public void setVertex(String vertex) {
		this.vertex = vertex;
	}
	public String getLabel() {
		return label;
	}
	public void setLabel(String label) {
		this.label = label;
	}
	
}







子图同构算法Ullmann实现，并采取了Refinement（java语言）