关于运输问题的—个等价定理

柯普曼和莱退尔所解决的空船航驶问题①,和我国图上作业法所解决的问题②,本质上是一致的,其判定条件不一样。本文目的在证明这两种判定条件等价,并论述几个有关问题。§1.等价定理设有运输网络[N,U],其中N 为点的集合,U 为边的集合,都是有限的。在每一边上可以来回运送,无容量限制,且距离相等。设N 的某些点上有物资待运,某些点上需要一定数量的物资,在一个方案中,有物资通过的边的集合为V,命[N,V]为     

关于偶图的一个定理及(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,Г),作网络如下;