题目：（例如）基于矩阵变换算法的图同构识别

设计人：张钦颖

学号：1414080901218

 

一、      实验环境：

1、硬件环境：个人机，CPU主频：4.01Ghz     内存：16G

2、软件环境：操作系统：win10

                     编程语言：C++

 

二、      实验任务解决方案：

1、          矩阵变换算法的流程图。

实验原理：

设两个无向图G=（V，E），G'=（V'，E'），当且仅当两图的邻接矩阵、行间同或矩阵、行间异或矩阵具有相同的行行置换时GG '同构。

矩阵算法步骤：

（1） 根据定义求出同型矩阵。

（2） 计算出行间同或矩阵，行间异或矩阵。

（3） 以图G=（v，E）的行间异或矩阵为参照，对行间异或矩阵的每一行，从异或矩阵搜索所有行，找到一个匹配。

①、   若不匹配，则两图不同构；

②、   若匹配，则继续往下判断执行。

（4） 判断邻接矩阵、行间同或矩阵中是否存在同样的匹配。

      ①、  若匹配存在，调整邻接矩阵、行间异或矩阵、行间同或矩阵，对应的行和列。

      ②、  若不匹配，则两图不同构。

  

2、矩阵变换算法实现的关键代码。

 

//冒泡排序

void wensen_mp(int mp[],int n)

{

 int t;

 for(int i=0;i<n-1;i++)

 {

  for(int j=0;j<n-1-i;j++)

  {

   if(mp[j]>mp[j+1])

   {

    t=mp[j];

    mp[j]=mp[j+1];

    mp[j+1]=t;

   }

  }

 }

}

 

/////////////////////////核心代码

//异或矩阵行转换

void wensen_hx(int **p1,int **p13,int **p14,int **p2,int **p23,int **p24,int n)

{

 int *p77=new int[n];//用于替换的临时一维数组存放p13

 int *p88=new int[n];//用于替换的临时一维数组存放p23

 int *p33=new int[n];//用于替换的临时一维数组存放p1

 int *p44=new int[n];//用于替换的临时一维数组存放p14

 int *p55=new int[n];//用于替换的临时一维数组存放p2

 int *p66=new int[n];//用于替换的临时一维数组存放p24

 int *p99=new int[n];//用于行行替换的临时数组

 int t;

 int tt;//进行跳转判断

 int ttt=0;//进行跳转判断

 

 //行行替换

 for( int i=0;i<n;i++)

 {

  //首先进行行赋值给另外一个数组p13

  for(int i77=0;i77<n;i77++)

  {

   p77[i77]=p13[i][i77];

  }

  //首先进行行赋值给另外一个数组p1

  for(int i33=0;i33<n;i33++)

  {

   p33[i33]=p1[i][i33];

  }

  //首先进行行赋值给另外一个数组

  for(int i44=0;i44<n;i44++)

  {

   p44[i44]=p14[i][i44];

  }

  //p77,p33,p44冒泡排序

  wensen_mp(p77,n);

  wensen_mp(p33,n);

  wensen_mp(p44,n);

  //开始进行比较,p12的每一行与p23的每一行进行比较

  for(int y=i;y<n;y++)

  {

   tt=0;

    //首先进行行赋值给另外一个数组

   for(int i88=0;i88<n;i88++)

   {

    p88[i88]=p23[y][i88];

   }

  

    //首先进行行赋值给另外一个数组

   for(int i55=0;i55<n;i55++)

   {

    p55[i55]=p2[y][i55];

   }

  

     //首先进行行赋值给另外一个数组

   for(int i66=0;i66<n;i66++)

   {

    p66[i66]=p24[y][i66];

   }

  

   //p88,p55,p66冒泡排序

   wensen_mp(p88,n);

   wensen_mp(p55,n);

   wensen_mp(p66,n);

 

   //开始比较

   for(int a=0;a<n;a++)

   {

    

    if(p77[a]==p88[a])

    {

     tt=a;

 

     if(a==n-1)//也就是各个都相等,找到匹配

     {

      //开始进行邻接矩阵对应位置比较

 

      for(int b=0;b<n;b++)

      {

       if(p33[b]==p55[b])

         {

        continue;

       }

 

       else if(b<n-1)

       {

        cout<<"不同构\n";

        return;

       }

      }

      //开始进行同或矩阵

      for(int c=0;c<n;c++)

      {

       if(p44[c]==p66[c])

       {

        continue;

       }

 

       else if(c<n-1)

       {

        cout<<"不同构\n";

        return;

       }

      }

 

      ttt++;//表示成功匹配一行

 

      //进行行行转换p2

      for(int u1=0;u1<n;u1++)

      { 

       t=p2[i][u1];

       p2[i][u1]=p2[y][u1];

       p2[y][u1]=t;

      }

 

      for(int u11=0;u11<n;u11++)

      {

       t=p2[u11][i];

       p2[u11][i]=p2[u11][y];

       p2[u11][y]=t;

      }

 

       //进行行行转换p23

      for(int u2=0;u2<n;u2++)

      {

       t=p23[i][u2];

       p23[i][u2]=p23[y][u2];

       p23[y][u2]=t;

      }

 

      for(int u22=0;u22<n;u22++)

      {

       t=p23[u22][i];

       p23[u22][i]=p23[u22][y];

       p23[u22][y]=t;

      }

 

 

       //进行行行转换p24

      for(int u3=0;u3<n;u3++)

      {

       t=p24[i][u3];

       p24[i][u3]=p24[y][u3];

       p24[y][u3]=t;

      }

 

      for(int u33=0;u33<n;u33++)

      {

       t=p24[u33][i];

         p24[u33][i]=p24[u33][y];

       p24[u33][y]=t;

      }

     break;

 

     }

     else

     {

      continue;

     }

    }

 

    else if(y==n-1)//一直循环到最后都未找到匹配

    {

    

     cout<<"不同构\n";

     return;

    }

    else

    {   

     break;

    }

   }

   //上面的匹配没有问题则进行行替换

 

   if(tt==n-1)

   {

   

    if(ttt==n)

    {

           cout<<"同构\n";

           return;

    }

    else

    {

      break; //成功跳出循环判断下一行

    }

   }

  }

 }

}

三、矩阵变换算法的计算复杂度分析（最好、最差、平均情况复杂度）：

       （1） 最好情况：n²+5*3n+32=O(n²)

      （2） 最差情况：5n³+15*6n²+88*5n+18=O(n³)

      （3） 平均复杂度：O(n²)

四、总结综合实验心得体会：

       同构图我们课上讲过许多，利用暴力法识别同构图我们也上过课，但是基于矩阵变换算法的图同构识别我就不会。由于矩阵变换算法为什么能识别同构图一点都不了解，所以我查阅了很多资料，当且仅当两图的邻接矩阵、行间同或矩阵、行间异或矩阵具有相同的行行置换时两个图是同构图，所以利用该原理，查阅了资料参考着写了代码。最后把该实验做了出来。

下面补充各种矩阵的定义：