均匀拟阵

特殊的拟阵

均匀拟阵(uniform matroid)是一种特殊的拟阵，设n≥r≥0是两个整数，E是一个含有n个元素的集合。如果I={X⊆E：|X|≤r}，则称(E，I)是一个均匀拟阵，记为Ur,n。

基本介绍

均匀拟阵是只以有限集E的子集I中包含元素的数目多少决定其独立性的拟阵Uk，n，其中n=|E|，E的子集B为拟阵的基，当且仅当B由k个元素组成。类似地，C为拟阵的圈，当且仅当C为k+1个元素组成。H为拟阵的超平面，当且仅当H由k-1个元素组成。例如，U2，3中的E视为欧氏空间里一条直线上的3点，每一个单点构成U2，3的超平面，每两点构成该拟阵的一个基，而全部三个点是它的惟一的圈。

广义均匀拟阵

一个拟阵(matroid)M是一个有序对(E，J)，其中E且是一个有限集合，J⊆2E是E中子集的集合，它们满足以下的公理：

(I1)∅∈I。

(I2)若I∈J，及I'⊆I，则I'∈J。

(I3)若I1，I2∈J且|I1|<|I2|，则存在e∈I2-I1使得I1∪e∈J。

E上的拟阵独立集系的全体记为(E)。

定义设n≥r≥0为两个整数，E是一个n元集，令

J={X⊆E:|X|≤r} ，

则(E，J) 是一个拟阵，这样的拟阵称为均匀拟阵。

定理1 设E 是一个有限集，B⊆E，m≤|B|，则令J( m，B，E) = { A∈2E||A∩B|≤m}∈(E) ，称J(m，B，E)是E上的关于集合B的m拟阵独立集系( 简称广义均匀拟阵独立集系) ，且称( E，J(m，B，E) ) 为关于集合B的带独立集系的m拟阵( 简称广义均匀拟阵) ，E 上的广义均匀拟阵的全体记为。

证明很显然J(m，B，E)满足I1和I2，

下面证明J(m，B，E) 满足I3，若A1，A2∈J(m，B，E) ，且|A1|<|A2|，下面证明存在e∈A2－A1使得|(A1∪{e})∩B|≤m，从而J(m，B，E) 满足I3。

情形一: 若|A1∩B||A2∩B|=m，存在e∈A2－B且e∈A2－A1，若不然有任意的e∈A2－B都有e∉A2－A1，即e∈A1，此时有|A1|=|A1∩B|+|A2－B|= m+|A2－B|=|A2∩B|+|A2－B|=|A2|，与|A1|<|A2|矛盾。此时有|(A1∪{e}) ∩B|=m≤m成立。

情形二: 若|A1∩B|

情形三: 若|A1∩B|>|A2∩B|，则一定存在e∈A2－A1，且有e∉B，此时有|(A1∪{e})∩B|=|A1∩B|≤m。

例1 取E = { 1，2，3，4，5} ，B = { 1，3，5} ( 本题中Jm,B= {I∈2B||I|≤m} ) ，则

J( 0，B)= {∅，{2} ，{4} ，E－B}=2E－B⊕J0,B，

J(1，B) = {∅，{1，2，4} ，{1，4} ，{1，2} ，{1} ，{2，3,4} ，{2，3} ，{3，4} ，{3} ，{2，4，5} ，{2，5} ，{4，5} ，{5} ，{2} ，{4} ，{2，4} } = 2E－B⊕J1,B，

J(2，B) = {∅，{1，2，4} ，{1，4} ，{1，2} ，{1} ，{2，3，4} ，{2，3} ，{3，4} ，{3} ，{2，4，5} ，{2，5} ，{4，5} ，{5} ，{2} ，{4} ，{2，4} ，{1，2，3，4} ，{1，2，3} ，{1，3，4} ，{1，3} ，{1，2，4，5} ，{1，2，5} ，{1，4，5} ，{1，5} ，{2，3，4，5} ，{2，3，5} ，{3，4，5} ，{3，5} }= 2E－B⊕J2,B，

类似的通过计算，可以得到

J(3，B) =2E－B⊕J3,B.

基于例1 可以发现并证明下面的广义均匀拟阵的构造定理：

定理2 设E是一个有限集，B⊆E，m≤|B| ，则

J(m，B，E) = 2E－B⊕Jm,B．

全国各地天气预报查询

上海市

市辖区

云南省

临沧市

云南省

丽江市