基于矩阵变换算法的图同构识别

题目:(例如)基于矩阵变换算法的图同构识别

设计人:张钦颖

学号:1414080901218

 

一、      实验环境:

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

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

                     编程语言:C++

 

二、      实验任务解决方案:

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

实验原理:

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

矩阵算法步骤:

(1) 根据定义求出同型矩阵。

(2) 计算出行间同或矩阵,行间异或矩阵。

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

①、   若不匹配,则两图不同构;

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

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

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

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

  1.png



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; //成功跳出循环判断下一行

    }

   }

  }

 }

}

2.png

3.png


三、矩阵变换算法的计算复杂度分析(最好、最差、平均情况复杂度):

       (1) 最好情况:n2+5*3n+32=O(n2)

      (2) 最差情况:5n3+15*6n2+88*5n+18=O(n3)

      (3) 平均复杂度:O(n2)



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

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

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


4.png





版权声明:若无特殊注明,本文为《Chin》原创,转载请保留文章出处。
本文链接:https://www.qinor.cn/post-58.html
正文到此结束

热门推荐

发表吐槽

你肿么看?

你还可以输入 250 / 250 个字

嘻嘻 大笑 可怜 吃惊 害羞 调皮 鄙视 示爱 大哭 开心 偷笑 嘘 奸笑 委屈 抱抱 愤怒 思考 日了狗 胜利 不高兴 阴险 乖 酷 滑稽

评论信息框
可使用QQ号实时获取昵称+头像

私密评论

吃奶的力气提交吐槽中...

已有2条吐槽

热搜

2019-08-26 01:23 广西河池市联通
文章不错非常喜欢
 Windows 7   Google Chrome 63.0.3239.132

repostone

2019-08-19 16:26 中国移动
非技术的路过。
 Windows 8.1 x64   Google Chrome 63.0.3239.132