拟阵多面体

拟阵多面体(matroid polytope)是一类多面体，它是拟阵上的优化问题所确定的多面体，设U=(J，F)为一个拟阵，其中J为一个有限集，F为独立集族，对于任何W⊆J，所有那些在包含意义下的W的极大独立子集均有相同的基数，即所含元素的数目相同，并且称这个数为W的秩，记为r(W)，拟阵的秩函数r是次模的，即对任何X，Y⊆J，均有r(X∪Y)+r(X∩Y)≤r(X)+r(Y)，多面体M(r)={x∈E+n|∑i∈wxi≤r(w)，对任何w⊆N}，其中N={1，2，…，n}，n=|J|，就称为拟阵多面体1。

基本介绍拟阵多面体是一种组合构形，它是由拟阵M=(E，I)的所有独立集的关联向量生成的多面体P。

记E={e1，e2，…，en}，独立集I的关联向量v(I)=(v1，v2，…，vn)，当I包含元素ei时，vi=1，否则vi=0，拟阵多面体的优越性在于，它可以借助拟阵的秩函数r而表示为约束不等式的形式I(E，r)：对于E的任意子集F，有

且对于E的任意元素e，有xe≥0，拟阵多面体P的顶点均为整值点，这样建立在拟阵上的优化问题就可以归结为不考虑其解是否取整数值的一般线性规划问题，从而为拟阵上的优化问题开辟了一个新的领域，例如，下图G上的图拟阵M(G)，其多面体由下述不等式决定1：

xe1≤1，xe2≤1，xe3≤1，xe4≤1，

xe1+xe4≤2，

xe2+xe4≤2，

xe3+xe4≤2，

xe1+xe2+xe3≤2，

xe1+xe2+xe4≤3，

xe1+xe3+xe4≤3，

xe2+xe3+xe4≤3，

xe1+xe2+xe3+xe4≤3，

xe1≥0， xe2≥0， xe3≥0， xe4≥0.

在以约束不等式表示的拟阵多面体里，若以G的满足下述条件的一般整值次模函数f取代拟阵的秩函数：

1.f(∅)=0；

2.对于E的任意子集A，B，若A⊆B则：

f(A)≤f(B)；

3.对于E的任意子集A和B，有

则不等式组I(E，f)决定的多面体，其顶点仍对应于某个拟阵的独立集，由I(E，f)决定的拟阵称为多面体拟阵1。

相关介绍多面体拟阵是一类整多面体，设为n维欧氏空间的那个非负象限，在上定义一个偏序：对于x，y∈，x≤y表示xi≤yi，i=1，2，…，n，设D⊆，若x0∈D具有这样的性质：不存在x∈D，x≠x0，使得x≤x0，则称x0为偏序D上的一个极小元，若不存在x∈D，x≠x0，使得x≥x0，则x0为D上的一个极大元，在上的一个有界多面体拟阵就是这样的一个多面体M，它具有性质：

1.若0≤y≤x，x∈M，则y∈M；

2.对任何a∈，集合Ma={x∈M|x≤a}的所有极大元的分量和均相同，并且，这个和称为a的秩；

在上所定义的秩确定一个多面体拟阵的秩函数，在N={1，2，…，n}的所有子集形成的簇2N上定义的函数ρ，若对任何U，W∈2N均有

ρ(U)+ρ(W)≥ρ(U∪W)+ρ(U∩W)，

则称ρ为次模的，若上面的不等式是反向的，则称ρ为上模的，一个多面体M⊆是有界多面体拟阵，当且仅当在2N上存在一个非降的次模函数ρ(W)，ρ(∅)=0，使得

M={，对任何W⊆N}.

在上的一个无界多面体拟阵就是这样的一个多面形Q，使它具有性质：若y≥x，和x∈Q，则y∈Q;对任何a∈，在Qa={x∈Q|x≥a}中的每个极小元的分量和都相同.一个多面形Q⊆是一个无界多面体拟阵，当且仅当存在2N上的一个上模函数ρ(W)，ρ()=0，使得1

Q={，对任何W⊆N}.

本词条内容贡献者为:

任毅如 - 副教授 - 湖南大学