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


Regular (2, 2)-systems
Authors:Reinhardt Euler
Affiliation:(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 = {e1, ctdot,en}, whose elements are orderede1 le ctdot leen. (E,I) is called regular, if the independence of {el, ctdot,elk},l1 < ctdot <lk, implies that of {eml, ctdot,emk}, whereml < ··· <mk andl1 lem1, ctdot,lk lemk. (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 isinC(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号