图的同构和Girth问题

1、图的同构和Girth问题Requirement图同构问题Unsolvedproblemincomputerscience:Canthegraphisomorphismproblembesolvedinpolynomialtime?我才疏学浅，不讨论那些高深的话题，我只讲一讲最基础的实现方式，用backtracking，然后检查是否符合要求。基本思想是检查两个图中的每个点是否相对应。也就是说，图p中的A点和B点间有一条边，那么图g中也得有这么两个点，M和N间有一条边；如果图p中A和B间没有边，那么图g中相对应的那两个点，也不可以有边。用backtracking遍历每种情况，然后checkEdge

2、s()。下面是伪代码boolDFS(intn,intlevel,intgraphl,intgraph2,intused,intperm)boolresult=false;if(level=-1)result=checkEdges(n,graph1,graph2);elseindexi=0;while(i0&same=true)if(graph1xy!=graph2permxpermy)same=false;y+;returnsame;这个算法的时间复杂度是0(N2*N!),N是顶点的数量。GirthofGraph不知道怎么翻译，就用Girth吧。反正就是在一个图中存在的最小圆环。我们老师pdf

3、上的定义是:TheshortestcycleinagraphGiscalledthegirthofG.如果我们把图用树的结构样式画出来，那么其实就很容易看出来怎么求那个小圆环了。比如下面这个小图:我们可以画一棵相应的小树:其实这里我们就能看出来，2这个点是4和6的共同的孩子节点。那么我们只要bfs遍历这棵树，找到这个共同的节点就好了。用一个iabel去标识走过的点，2会走两遍，第二次经过它的时候就知道它这里有个环了。因为我用的swift做project的，所以我用的是array来做的。我刷leetcode用的是java。C+太麻烦了，还是不用了。因为我们老师还要我们plot出不用节点数的图的时

4、间的performanceSwift还有个好处就是我可以用iOS作图，比较方便。而且swift的array可以当linkedlist用。但是我们还是可以做一个node来存储没个点的深度信息depth。classNodepublicintvertex,depth;publicNode(intvertex,intdepth)this.vertex=vertex;this.depth=depth;其实用什么语言都无所谓，如果你用java，你可以用ArrayDeque()，或者LinkedList()，C+的话可以用std:queue，都差不多。下面是bfs遍历的主要过程：while(node!=nu

5、ll&short3&(node.depth+1)*2-1short)intdepth=node.depth+1;for(intneighborinnode.vertexsallneighbor)/ifwehaventwentthroughthisneighborif(labelneighbor0)queue.add(newNode(neighbor,depth);labelneighbor=depth;elseif(labelneighbor=depth-1)/oddneighborsif(depth*2-1short)short=depth*2-1;elseif(labelneighbor=

6、depth)/evenneighborsif(depth*2short)short=depth*2;/goanothernodenode=queuesfirstelement,andremovethefirstelement;/startanewbfsfromanothervertexremoveallelementsfromqueue;root+;遂藝娄浚趣殘技浚趣邈遐趣藝娄浚邂憑娄浚趣邈遐娄$護技浚翅發技浚趣邈遐娄建護黴第藝後裁趣浚技裁銀翅護装裁趣浚技裁斑殊妄裁翅護甕娈趣圾後裁趣燧妄裁翅護甕娈翅藝後裁趣務第我们都知道bfs的时间复杂度是O(m+n)，其中m和n分别是点和边的数量。因为这个算法需要尝试每个点作为root，从每个点都出发做一次bfs寻找最小圈，所以外层还有个循环，while(root3)-所以时间复杂度是O(n*(m+n)。References:Wikipedia-Girth(graphtheory)Wikipedia-Graphisomorphismproblemcs.umu.seOptimalalgorithmforfindingthegirthofasparsegraph?-Theoreti