补充资料：覆盖与填装

覆盖与填装
covering and packing

覆盖与填装!~ring and Packing .1喇狱p，胶“”班‘皿洲} 关于一个集合到另个集合的多值映射的组合构形.设已给定集合E和卜r是从厂到F中的多值映射，r(e)是元e任E在r作用「的象，并对任(”三E记r(C)=娜‘、。r(e)·子集f资E称为对于(F，石，f’)的一个覆盖(①vering)，如果f一传)=厂.子集尸三打称为对于(F，万，F)的一个填装(packing)，如果对p中任意两个不同兀“和e，集合I一(ez)和I”伙)不相交子集尸生E称为完满填装(perfectpa南ng)或完满褪盖(pe成ct以)vering)，如果尸既是填装又是援盖.集合￡称为覆盖集(covering set)，f称为被覆盖集(田voredset).如果逆映射I一’使得r’(川二￡，则可把f当作覆盖集而把五当作被覆盖集.映射I一’:厂一，f定义了一个关联关系(jn面den优relaijt)n)丈对于元砂e卜一和亡任五若有。〔r(时，则。和e相关联(记为。Ie). 填装与覆盖的概念联系着一些极值问题:对给定的(r.E，f飞寻求对于某些泛函取得极值的填装净覆盖.这种泛函，举例来说，可以通过给E的每个儿e赋以非负实数权w(e)来规定.最小覆盖问题乃是构造-个覆盖c使得艺。。。、(e)取极小值.通常研究、(。)二，的情形、这是关系到求极小基数的覆盖，或所谓最小覆盖(least的vering)的I可题 如果‘r，E，r)使得 甲赞{r(“)}(比钾川r’(时}异以则覆盖的最小基数以r，E，均满足不等式 }vl_，，、，、、_」石{In{;l、 一《划厂.L.I’、石l一干二}二二上二一二二一} “岭}}七};在关于填装问题的极值问题中，通常要求得最大基数的填装二有时在被覆盖集V上定义了取非负整数值的函数又，则满足下述条件的子集尸三E称为又覆盖以一covering)以填装以·Packing)):对每个v〔V，与v关联的元e6尸的个数a和，P)适合不等式 叮(。

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