矩阵论中的图论匹配法

Matching method of graph theory in matrix theory

G.Birkhoff用代数的方法证明了如果一个矩阵是双随机矩阵,则它能表示成置换矩阵的凸线性组合.设G是具有两分类(X,Y)的二部图,则G中含有饱和X中的所有顶点的匹配M的充分必要条件为:对S■X,有dG(S)≥|S|.文章借助上述二部图的匹配思想,给出这一结论的图论证明.

Let a non-negative real matrix Q be doubly stochastic,and a permutation matrix be a（0,1）-matrix which has exactly one 1 in each row and each column,then every permutation matrix will be doubly stochastic matrix.G.Birkhoff proved a conclusion that every doubly stochastic matrix Q can be expressed as a convex linear combination of permutation matrixs using the method of algerbra.Let G be a bipartite graph with bipartition（X,Y）,then G contains a matching M that saturates every vertex in X if and only if dG（S）≥｜S｜ for all S X.In this paper,we obtain the proof of graph theory on the conclusion using the above matching theorem of bipartite graph.