| 求偶图最大匹配的矩阵算法 |
| |
| 引用本文： | 代西武,李群高.求偶图最大匹配的矩阵算法[J].北京建筑工程学院学报,2003,19(2):75-78. |
| |
| 作者姓名： | 代西武 李群高 |
| |
| 作者单位： | 基础部,北京,100044 |
| |
| 摘 要： | 深入研究了偶图与其简化邻接矩阵之间的关系，提出了(0，1)—矩阵的无关元对角形概念，利用此概念给出了定理“任一(0，1)—矩阵的项秩与线秩相等”的一种直接简单证明，得到了判断(0，1)—矩阵的无关元集为最大无关元集的充要条件。最后给出了寻找偶图最大匹配的算法——矩阵算法，该算法与匈牙利算法比较具有较高的运算效率和易于在计算机上实现等优点。
|
| 关 键 词： | 偶图 匹配 矩阵算法 无关元集 计算机 |
| 文章编号： | 1004-6011(2003)02-0075-04 |
| 修稿时间： | 2002年12月9日 |
The Matrix Algorithm of Search a Maximum Matching in Bipartite Graph |
| |
| Dai Xiwu Li Qungao.The Matrix Algorithm of Search a Maximum Matching in Bipartite Graph[J].Journal of Beijing Institute of Civil Engineering and Architecture,2003,19(2):75-78. |
| |
| Authors: | Dai Xiwu Li Qungao |
| |
| Abstract: | |
| |
| Keywords: | bipartite graph (0 1)-matrix diagonal matrix of an irrelative element set maximum matching |
| 本文献已被 CNKI 维普 万方数据 等数据库收录！ |
