新的二部图判定算法

New algorithm of bipartite graph decision

二部图是现代图论中一类非常重要的图,然而关于其判定的充要条件却很少,而且用算法实现它们很复杂,需要指数级的时间代价。利用图的广度优先遍历,提出了一个易于实现的二部图判定的充要条件:无向图G是二部图当且仅当G的广度优先生成森林中的同一层上的任意两点在G中不邻接。给出了该判定条件的实现算法,算法的时间复杂度是O(n2),很好地解决了二部图的判定问题。

Bigraph is an important graph in modern graph theory. However, there are few sufficient conditions to decide the Bigraph. Moreover, it is very complicated to implement them through algorithms, which need exponential time complexity. Based on the breadth first search, the paper proposed a new sufficient condition of Bigraph which is easy to be implemented. The sufiqcient condition is： a necessary and sufficient condition of undirected graph G is the Bigraph, which is the arbitrary two vertexes in the same level of the breadth first spanning forest of the G are not adjacent in the G. The paper put forward the new algorithm of the condition, the time complexity of which is O（n2）. Therefore, the paper solves the problem of Bigraph decision successfully.