求偶图最大匹配的矩阵算法

• 作者: 代西武 李群高
• 来源期刊: 北京建筑工程学院学报
• 学科: 数学
• 关键词: 偶图 (0,1)-矩阵 无关元对角形 最大匹配
• 年，卷（期）: 2003,（2）
• 页码范围: 75-78
• 页数: 4页
• 分类号: O157.5:O241.6
• 字数: 2390字
• 语种: 中文
• DOI: 10.3969/j.issn.1004-6011.2003.02.020

摘要

深入研究了偶图与其简化邻接矩阵之间的关系，提出了(0，1)-矩阵的无关元对角形概念，利用此概念给出了定理“任一(0，1)-矩阵的项秩与线秩相等”的一种直接简单证明，得到了判断(0，1)-矩阵的无关元集为最大无关元集的充要条件。最后给出了寻找偶图最大匹配的算法——矩阵算法，该算法与匈牙利算法比较具有较高的运算效率和易于在计算机上实现等优点。