k-正则偶图对集矩阵的分解定理

DECOMPOSITION THEOREMS ON THE BIPARTITION MATRICES OF k REGULAR BIPARTITITE GRAPHS

证明了一个ｎ阶非负实矩阵可分解为某些ｎ阶置换矩阵的线性组合的定理，由此得到了ｋ－正则偶图的对集矩阵的分解定理．这些定理及其证明给出了ｋ－正则偶图的完美匹配的构造方法，并举例说明对集矩阵的分解不是唯一的．

In this paper we prove a theorem, which says that a nonnegative real matrix of order n can be decomposited into a linear combination of some permutation matrices of order n . It follows that decomposition theorems on the bipartition matrices of k regular bipartite graphs are obtained. These theorems and their proofs show a structural method for finding the perfect matchings of a k regular bipartite graph. We present an example to show that the decomposition of a bipartition matrix is not unique.