关于偶图的一个定理及(0,1)—矩阵的项秩

寇尼希曾给出一个著名的定理1,2]:在偶图(X,Y,T)上极大对集所含的弧数,等于其极小负荷集所合的点数。傲尔(o.are)2,3]更给出这个数为ρ—δ_0,其中ρ=|X|为X 所含的点数,δ_0=_(A(?)X)~max(|A|—|ГА|)为点集X 的极大欠数。本文运用上面的定理,及极小截量定理4.5],给出一个与此类似的定理(定理2)。使用本文定理1,可以求得相应的(0,1)—矩阵的项秩(定理4)及正规类■(R,S)的极小项秩和具极小项秩的矩阵(定理5)。本文最后使用同样的思想,再从极大对集的意义给出(0,1)—矩阵项秩及正规类■(R,S)极小项秩的另一计算公式(定理7,8)。§1.关于偶图的一个极大极小定理。定理1.已给无孤立点的偶图(X,Y,Г),作网络如下;