首页 | 本学科首页   官方微博 | 高级检索  
     检索      


Regular (2, 2)-systems
Authors:Reinhardt Euler
Institution:(1) Mathematisches Institut, Universität zu Köln, Weyertal 86, D-5 Köln 41, West Germany
Abstract:Let (E,I) be an independence system over the finite setE = {e 1, ctdot,e n }, whose elements are orderede 1 le ctdot lee n . (E,I) is called regular, if the independence of {e l , ctdot,e l k },l 1 < ctdot <l k , implies that of {e m l , ctdot,e m k }, wherem l < ··· <m k andl 1 lem 1, ctdot,l k lem k . (E,I) is called a 2-system, if for anyI isinI,e isinE setmnI the setI xcup {e } contains at most 2 distinct circuitsC, Cprime isinI and the number 2 is minimal with respect to this property. If, in addition, for any two independent setsI andJ the family (C setmn J, C isin C (J, I)), whereC(J, I) denotes {C isinC:existe isinJ setmnI C 
$$ \subseteq $$
xcup {e}}, can be partitioned into 2 subfamilies each of which possesses a transversal, then (E,I) is called a (2, 2)-system. In this paper we characterize regular 2-systems and we show that the classes of regular 2-systems resp. regular (2, 2)-systems are identical.
Keywords:Independence System  Matroid  Regularity  Knapsack Problem
本文献已被 SpringerLink 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

Copyright©北京勤云科技发展有限公司  京ICP备09084417号