均匀拟阵
特殊的拟阵
均匀拟阵(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.
参考资料
广义均匀拟阵.知网空间.2017-6
最新修订时间:2022-08-25 16:13
目录
概述
基本介绍
广义均匀拟阵
参考资料