1.基于K2-MDD的大规模图的最大公共连通子图匹配方法，其特征是，包括步骤如下：

步骤1、根据K2树的规则分别对目标图和匹配图的顶点进行编码；

步骤2、依据目标图和匹配图的顶点编码，对目标图和匹配图的边进行编码，每条边的编码为该条边的2个顶点的编码进行按位和；

步骤3、根据目标图和匹配图的边的编码构造多值决策图结构，由此得到目标图和匹配图的K2-MDD结构图；

步骤4、在构建的目标图和匹配图的K2-MDD结构图中，利用符号决策图的逻辑交运算分别求出目标图和匹配图中各个顶点的度；

步骤5、基于目标图和匹配图中各个顶点的度，对目标图和匹配图的进行匹配，即：

步骤5.1、先选择目标图中度最高的顶点x1和匹配图中度最高的顶点y1，将顶点对(x1，y1)加入到最大公共连通子图集合Z中；再将目标图的顶点x1和匹配图的顶点y1的度置0；后判断目标图中与顶点x1具有相邻边的顶点的度是否大于0：如果是，则将与顶点x1具有相邻边的顶点的度减1；否则，与顶点x1具有相邻边的顶点的度不作调整；同时判断匹配图中与顶点y1具有相邻边的顶点的度是否大于0：如果是，则将与顶点y1具有相邻边的顶点的度减

1；否则，与顶点y1具有相邻边的顶点的度不作调整；

步骤5.2、先从目标图中选择与顶点x1具有相邻边且度最高的顶点x2，以及从匹配图中选择与顶点y1具有相邻边且度最高的顶点y2，将顶点对(x2，y2)加入到最大公共连通子图集合Z中；再将目标图的顶点x2和匹配图的顶点y2的度置0；后判断目标图中与顶点x2具有相邻边的顶点的度是否大于0：如果是，则将与顶点x2具有相邻边的顶点的度减1；否则，与顶点x2具有相邻边的顶点的度不作调整；同时判断匹配图中与顶点y2具有相邻边的顶点的度是否大于0：如果是，则将与顶点y2具有相邻边的顶点的度减1；否则，与顶点y2具有相邻边的顶点的度不作调整；

步骤5.3、先从目标图中选择与顶点xi具有相邻边且度最高的顶点xi+1，以及从匹配图中选择与顶点yi具有相邻边且度最高的顶点yi+1，将顶点对(xi+1，yi+1)加入到最大公共连通子图集合Z中；再将目标图的顶点xi+1和匹配图的顶点yi+1的度置0；后判断目标图中与顶点xi+1具有相邻边的顶点的度是否大于0：如果是，则将与顶点xi+1具有相邻边的顶点的度减1；否则，与顶点xi+1具有相邻边的顶点的度不作调整；同时判断匹配图中与顶点yi+1具有相邻边的顶点的度是否大于0：如果是，则将与顶点yi+1具有相邻边的顶点的度减1；否则，与顶点yi+1具有相邻边的顶点的度不作调整；其中i＝2，3，4，…，l-1；

步骤5.4、依次迭代步骤5.3，直到目标图中与顶点xl具有相邻边的所有顶点的度全部为

0或匹配图中与顶点yl具有相邻边的所有顶点的度全部为0，此时完成目标图和匹配图的匹配，输出最大公共连通子图集合Z＝{(x1，y1)，(x2，y2)，…,(xi+1，yi+1)，…，(xl，yl)}。

2

2.根据权利要求1所述的基于K-MDD的大规模图的最大公共连通子图匹配方法，其特征是，步骤1中，目标图和匹配图的每个顶点的编码的位数为n位，其中 K是大于等于2的整数，|V|是顶点数。