【作者】 李小强； 张宁；

【Author】 LI Xiao-qiang,ZHANG Ning University of Shanghai for Science and Technology,Shanghai 200093,China

【机构】 上海理工大学管理学院；

【摘要】 本文应用邻接矩阵的特征向量对二部图进行判别。计算任意连通图的邻接矩阵最小特征值对应的特征向量,并根据该特征向量各分量符号将节点划归两类,如果该图的边恰好全在这两类节点之间,则该图为二部图,同时得到该二部图的顶点划分;否则,该图不是二部图。该方法的核心是证明任意连通二部图的邻接矩阵最小特征值所对应的特征向量的各分量非零,且同号分量对应于同类节点。最后,我们将该方法应用于两个实例图,实验结果表明,该方法是有效的。对于庞大的复杂网络,可以用幂法间接求出最小特征值,然后用该方法对图进行判别。更多还原

【Abstract】 Based on adjacent matrix,a distinguish algorithm is proposed for bipartite graph.Calculate the corresponding eigenvector of the minimum eigenvalue of the adjacent matrix of an arbitrary connected bipartite graph,and separate the node into to group depend on the sign of the element of eigenvector.If all the edges of the studied graph sit between two groups,the studied graph is a bipartite graph,and obtains the partition of it;otherwise,the studied graph is not a bipartite graph.The hard-core is to demonstrate that the element of the corresponding eigenvector of the minimum eigenvalue of the adjacent matrix of an arbitrary connected bipartite graph is not zero;the corresponding nodes of the same sign elements sit in the same group.At last,we use this algorithm to distinguish two example graph,the results show that this algorithm is feasible.To deal with the large complex network,we can firstly use the power method to calculate the minimum eigenvalue indirectly,and then apply this algorithm to distinguish it.更多还原