补充资料：相异代表系

相异代表系
ystem of different representatives i?K system of distinct representatives

　　相异代表系[system‘d旅r印tr印rese，tatiVes或s”tem of distinct卿resentatives;p幻月“，”“x npe皿-ev”班Te几e盆eoeTeMa]，时于集合S的一个给定子集，族犷二{F，:沁科的 由具有如下性质的一一映射川I~S所确定的集合R二{二(i):i任I圣:对任意i任I，有二(i)〔F(i)(这里I是指标集).相异代表系R的另一个名字是族，，的横截(transversal for the fanllly).人们也讨论族，，的部分横截(partial transversal ofa云lm口y)，即疮如{升(’i)，=i’e全.，}的集合，其中I。是I的子集，并凤二:I。i一S是一一映射. 相异代表系被用于纯组合数学研究以及线性规划、数理经济和控制论的应用.在组合数学框架里，相异代表系在选择问题和极值问题中起着重要作用.特别是在拉丁方的研究、指派问题、各种极值问题和极小一极大定理、以及给定行和与列和限制的非负矩阵的研究中，相异代表系都有应用. 对有限集I，相异代表系存在的准则由P】1汕P南11定理(P肠吐ip Halltheoreln)给出:假设.犷二{F:i曰}是集合S上的一个子集族，11}二n是有限数，则厂有相异代表系，当且仅当对每一个k(瓦二1，…，，，)，和每一个k元子集遥11，…，i*}91，有IF‘。日一口兀‘})k.Hall的定理等价于关于O一1矩阵的助nig的定理(见选择定理(selection theo~))，当每一个F，(派任I)是有限时，这个基本准则也适用I是无穷集的情况.粗略地说，一些例子表明，这些情形穷尽了Hall准则的可应用性的范围，但在其他一些情形它可作各种准则的出发点(见【3』).例如:a)当有子集I(， C=I，使I一I。，有限，并且对所有i任I。，F:都有限时;或者b)当I是可数集时. 由于相异代表系有广泛的应用，所以实际确定它们的算法(【1」)很有意义. 关于相异代表系的主要问题之一是有限集的有限族的相异代表系的个数问题;它与0一1矩阵的积和式(详rmanent)的计算有关.关于相异代表系的个数有一些下界.设族，一是由n个子集F、，…，F。组成，其基数大小的顺序为m=}F且】续…簇}F。}.若了满足Hafl准则，则相异代表系的个数至少是 盯四(阴，n) n(IF*卜k+l)· k一I关于代表系问题在拟阵(Inatroid)(也称为独立空间或组合几何(combinat面alge~try”理论中也有讨论.Ednlonds一Fu」kerson定理(Ednl以15~F川ke介幻nl」le-orem)给出了代表系理论和拟阵之间的联系:给定一个有限集的子集族，它的所有部分横截的总体是某个拟阵的所有独立子集的总体.由族犷按上述方式得到的拟阵称为.犷的横截拟阵(tlansversallr坦tmid).许多拟阵能够表示为某个集族的横截拟阵. 相异代表系的概念可以在不同的方向上进行推广，例如:a)给定族‘犷={F、，，二，F。}和整数向量p二(户，，一’，户。)，户横截(户一transversal)是集合{二(l)，一二(n)}，其中对i=z，二，n，二(i)三r，是S的两两不交的子集且满足1(}7t(i)}簇p‘;b)对犷={F.:i任I}和整数k)l，k横截(k一transversal)是由映射东I~S所确定的子集R={7r(i):沁科，其中二(i)C=几一且满足1簇}{7T一’(武i))}}簇k，沁I
　　

说明：补充资料仅用于学习参考，请勿用于其它任何用途。