鸿 网 互 联 www.68idc.cn

当前位置 : 服务器租用 > 手机系统开发 > J2ME > >

How to find a cycle of length 4?

来源:互联网 作者:佚名 时间:2015-09-25 05:41
此处说的环是一个简单环。 假设图是用邻接矩阵实现,邻接矩阵记为 $A$ ,节点个数为 $n$,边的个数为 $m$。 如果存在 $i,j$,且 $1 \le ij \le n$ ,$N(i) \cap N(j) \ge 2$ ,则说明存在一个长度为 4 的环。 算法如下: 1 for (i=1 to n) 2 for ( int j=i+1

此处说的“环”是一个简单环。

假设图是用邻接矩阵实现,邻接矩阵记为 $A$ ,节点个数为 $n$,边的个数为 $m$。

如果存在 $i,j$,且 $1 \le i<j \le n$ ,$N(i) \cap N(j) \ge 2$ ,则说明存在一个长度为 4 的环。

算法如下:

 1 for(i=1 to n)
 2     for(int j=i+1 to n)
 3         count = 0;
 4         for(int k=1 to n)
 5             if(A[j][k]==A[i][k]==1)
 6                 count++;
 7         if(count>=2)
 8             return "exist a cycle of length 4";
 9 return "not exists";

算法复杂度:$O(n^3)$

算法正确性证明:

命题:如果存在 $i,j$,且 $1 \le i<j \le n$ ,$N(i) \cap N(j) \ge 2$ ,则存在一个长度为 4 的环。

证明. 

从上图可以看出, $i \rightarrow b \rightarrow j \rightarrow a \rightarrow i$ 是一个长度为 4 的环。

命题:如果存在一个长度为 4 的环,则存在 $i,j$,且 $1 \le i<j \le n$ ,$N(i) \cap N(j) \ge 2$。

证明.

已知图中存在一个长度为 4 的环,如 $a \rightarrow b \rightarrow d \rightarrow c \rightarrow a$,则 $N(a) \cap N(d)=\{c,b\}$,因此得证。

 

 

网友评论
<