摘要
深入研究了偶图与其简化邻接矩阵之间的关系 ,提出了 (0 ,1 ) -矩阵的无关元对角形概念 ,利用此概念给出了定理“任一 (0 ,1 ) -矩阵的项秩与线秩相等”的一种直接简单证明 ,得到了判断 (0 ,1 ) -矩阵的无关元集为最大无关元集的充要条件。最后给出了寻找偶图最大匹配的算法———矩阵算法 。
In this paper, bipartite graph and its reduced adjacency matrix are studied, and the concept of diagonal matrix of an irrelative element set is given. We give a short proof of the theorem: in a (0,1)-matrix the term rank equals the line rank. The theorem is obtained: in a (0,1)-matrix, an irrelative element set F is maximum irrelative element set if and only if that there is a line cover Γ with |Γ|=|F|. In the end, the matrix algorithm of search a maximum matching in bipartite graph is given.
出处
《北京建筑工程学院学报》
2003年第2期75-78,共4页
Journal of Beijing Institute of Civil Engineering and Architecture
关键词
偶图
匹配
矩阵算法
无关元集
计算机
bipartite graph
(0,1)-matrix
diagonal matrix of an irrelative element set
maximum matching
