首页 > 代码库 > 图论----同构图(详解)
图论----同构图(详解)
图论当中的术语，假设G=(V,E)和G1=(V1，E1)是两个图，如果存在一个双射m：V→V1，使得对所有的x,y∈V均有xy∈E等价于m(x)m(y)∈E1，则称G和G1是同构的,这样的一个映射m称之为一个同构，如果G=G1，则称他为一个自同构。
简单来说，同构图的结点数必须相同，结构必须相同。
如图3.6，第一个图形和第二个图形的区别在于环的数量。第一个图形为一个环，第二个为两个环，所以不是同构图。
若删去z1和u1，删去v1和w1，连接z1和w1，成为一个v1u1的链和z1w1x1y1的环，依旧不是同构图，因为必须环数相同，链数相同。
但这还是缺少一个条件，比如图形A存在两个环a1和a2，a1有3个结点，a2有5个结点，图形B也有两个环，b1有4个结点，b2有4个结点，依旧不是同构图，这里的条件就是环上或链上的借点数相同，和结点顺序无关。
引入例题，HDU3926-Hand in Hand ，判断两次组成的图形是否是同构图。
思路之一：通过并查集确定环数/链数，和环内/链内的人数，再排序进行比较。
排序时按照人数排序，若人数相同要按照状态排序。注意这几点或许会比较容易过。
请先自己进行尝试，尝试后再参考代码。
1 #include<iostream> 2 #include<cstring> 3 #include<cstdio> 4 #include<math.h> 5 #include<vector> 6 #include<algorithm> 7 #include<queue> 8 #include<set> 9 using namespace std; 10 int pre[10100]; 11 struct e{ 12 int a,b; 13 }; 14 e s1[10010]; 15 e s2[10010]; 16 int find(int x) 17 { 18 while(x!=pre[x]) 19 x=pre[x]; 20 return x; 21 } 22 int cmp(e a,e b){ 23 if(a.a==b.a) return a.b>b.b; 24 else return a.a>b.a; 25 } 26 void init(int n) 27 { 28 for(int i=1;i<=n;i++) 29 pre[i]=i; 30 } 31 int main() 32 { 33 int t,cas=1;; 34 scanf("%d",&t); 35 while(t--) 36 { 37 for(int i=1;i<10010;i++) 38 { 39 s1[i].a=1;s1[i].b=0; 40 s2[i].a=1;s2[i].b=0;//最开始每个都是独立的，默认为链 41 } 42 bool flag=false; 43 int n1,m1,n2,m2; 44 45 scanf("%d%d",&n1,&m1); 46 init(n1); 47 for(int i=0;i<m1;i++) 48 { 49 int a,b; 50 scanf("%d%d",&a,&b); 51 int dx=find(a); 52 int dy=find(b); 53 if(dx!=dy) 54 { 55 pre[dx]=dy; 56 s1[dy].a+=s1[dx].a; 57 s1[dx].a=0;//把拉手的孩子数量加起来，下同 58 } 59 else s1[dy].b=1;//成环 60 } 61 62 scanf("%d%d",&n2,&m2); 63 init(n2); 64 for(int i=0;i<m2;i++) 65 { 66 int a,b; 67 scanf("%d%d",&a,&b); 68 int dx=find(a); 69 int dy=find(b); 70 if(dx!=dy) 71 { 72 pre[dx]=dy; 73 s2[dy].a+=s2[dx].a; 74 s2[dx].a=0; 75 } 76 else s2[dy].b=1; 77 } 78 if(n1==n2){ 79 80 sort(s1+1,s1+n1+1,cmp); 81 sort(s2+1,s2+n2+1,cmp);//排序，若孩子的数量相同则对是否是环进行排序，这里要注意 82 83 for(int i=0;i<n1;i++) 84 if(s1[i].a!=s2[i].a||s1[i].b!=s2[i].b) {//判断数量，状态 85 flag=true; 86 break; 87 } 88 } 89 if(n1!=n2) flag=true; 90 91 if(flag) printf("Case #%d: NO\n",cas++); 92 else printf("Case #%d: YES\n",cas++); 93 } 94 return 0; 95 }
图论----同构图(详解)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。