1、 题目： （例如）基于矩阵变换算法的图同构识别题目： （例如）基于矩阵变换算法的图同构识别 一、 实验环境： 1、硬件环境：个人机，CPU 主频：2.3GHZ 内存：4GB 2、软件环境：操作系统：windows 编程语言：C+ 二、 实验任务解决方案： 实验思路：设两个无向图 G=(V,E),G=(V,E),G,G同构当且仅当两图的邻接矩 阵、行间同或矩阵、行间异或矩阵具有相同的行行置换。 1. 矩阵算法步骤 a. 根据定义，求出同型矩阵 AAG、AAG. b. 计算出行间同或矩阵 RAG、RAG，行间异或矩阵 RXG、RXG. c. 以图 G=(V,E)的行间异或矩阵为参照， 对 RXG
2、的每一行， 从 RXG搜索所有行， 找到一个匹配。若不存在相应匹配，则两图不同构；若匹配，转步骤（4）. d. 判断邻接矩阵 AG、AG,行间同或矩阵中是否存在同样的匹配，若匹配存在， 调整邻接矩阵 AG、行间异或矩阵 RXG、行间同或矩阵 RAG对应的行和列； 若不匹配，则不同构. 2、基于矩阵变换算法的流程图。 输入图一邻接矩阵 输入图二邻接矩阵 由图一邻接矩阵求出同型矩阵、异或矩阵、同或矩阵 由图二邻接矩阵求出同型矩阵、异或矩阵、同或矩阵 以图一异或矩阵为基准，判断 图二异或矩阵是否存在元素相同行 开始 不同构 结束 对应的行中图一的邻接矩 阵与图二的邻接矩阵是否元素相同； 图一的同或矩
3、阵和图二的 同或矩阵是否相同 否 是 否 对图二的同型矩阵、异或矩阵、 同或矩阵呢对应位置进行行行转 换：即对应行变换，对应列变换 判断是最后一行 是 同构 是 否 3、基于矩阵变换算法实现的关键代码。 /*冒泡排序 void wensen_mp(int mp,int n) int t; for(int i=0;in;/接收第一个图的顶点个数 if(cin.fail() coutp1i11j11; /接收第二个邻接矩阵的二维数组 coutp2i22j22; /* /图一同型矩阵 wensen_tx(p1,p12,n); /图一异或矩阵 wensen_yh(p1,p12,p13,n); /图一同
4、或矩阵 wensen_th(p1,p12,p14,n); /图二同型矩阵 wensen_tx(p2,p22,n); /图二异或矩阵 wensen_yh(p2,p22,p23,n); /图二同或矩阵 wensen_th(p2,p22,p24,n); /*输出 /* s=“图一邻接矩阵输出：“; out(p1,s,n); s=“图一同型矩阵输出：“; out(p12,s,n); s=“图一异或矩阵输出：“; out(p13,s,n); s=“图一同或矩阵输出：“; out(p14,s,n); s=“图二邻接矩阵输出：“; out(p2,s,n); s=“图二同型矩阵输出：“; out(p22,s,n); s=“图二异或矩阵输出：“; out(p23,s,n); s=“图二同或矩阵输出：“; out(p24,s,n); */ /*核心代码，进行行转换 coutss; return 0;
