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


Complementary bases of a matroid
Authors:TL Magnanti
Institution:Operations Research Center, Massachusetts Institute of Technology, Cambridge, Mass. 02139, USA
Abstract:Let e1, e1, e2, e2, …, en, en be the elements of matroid M. Suppose that {e1, e2, …;, en} is a base of M and that every circuit of M contains at least m + 1 elements. We prove that there exist at least 2m bases, called complementary bases, of M with the property that only one of each complementary pair ej, ej is contained in any base.We also prove an analogous result for the case where E is partitioned into E1, E2, …, En and the initial base contains |Ej| ? 1 elements from partition Ej.
Keywords:
本文献已被 ScienceDirect 等数据库收录!
设为首页 | 免责声明 | 关于勤云 | 加入收藏

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