| 新的二部图判定算法 |
| |
| 引用本文： | 王青松.新的二部图判定算法[J].计算机应用,2009,29(Z1). |
| |
| 作者姓名： | 王青松 |
| |
| 作者单位： | 辽宁大学,信息学院,沈阳,110036 |
| |
| 摘 要： | 二部图是现代图论中一类非常重要的图,然而关于其判定的充要条件却很少,而且用算法实现它们很复杂.需要指数级的时间代价.利用图的广度优先遍历,提出了一个易于实现的二部图判定的充要条件:无向图G是二部图当且仅当G的广度优先生成森林中的同一层上的任意两点在G中不邻接.给出了该判定条件的实现算法,算法的时间复杂度是O(n2),很好地解决了二部图的判定问题.
|
| 关 键 词： | 二部图 二部图判定 广度优先遍历 |
New algorithm of bipartite graph decision |
| |
| WANG Qing-song.New algorithm of bipartite graph decision[J].journal of Computer Applications,2009,29(Z1). |
| |
| Authors: | WANG Qing-song |
| |
| Affiliation: | College of Information;Liaoning University;Shenyang Liaoning 110036;China |
| |
| Abstract: | 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 sufficient 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... |
| |
| Keywords: | bipartite graph bipartite graph decision breadth first search |
| 本文献已被 CNKI 万方数据 等数据库收录！ |
|
