一种基于邻接矩阵的二部图判定算法  

Algorithm of Bipartite Graph Decision Based on Adjacency Matrix

作　　者：王敏[1] 韩俊英[1] 

机构地区：[1]甘肃农业大学信息科学技术学院

出　　处：《重庆理工大学学报（自然科学）》2011年第8期75-77,共3页Journal of Chongqing University of Technology：Natural Science

基　　金：甘肃省自然科学基金资助项目(096RJZA004)

摘　　要：在二部图定义的基础上,给出一种基于邻接矩阵的新判定算法,通过在每对结点间逐步插入中间结点进行路径长度检测,并进行了实验测试。结果表明,新算法能较好解决二部图的判定问题。Bipartite graph is an important graph in modern graph theory.However,there are few sufficient algorithms to decide the bipartite graph.According the definition of bipartite graph,a new decision algorithm based on adjacency matrix is introduced,which adds inner vertex between two vertexes to test length of path,we measure many data and the performance of experiment shows that the new algorithm solves the problem of bipartite graph decision successfully.

关 键 词：二部图判定 邻接矩阵 路径长度 奇圈 

分 类 号：TP391[自动化与计算机技术—计算机应用技术]