Complementary bases of a matroid |
| |
Authors: | TL Magnanti |
| |
Institution: | Operations Research Center, Massachusetts Institute of Technology, Cambridge, Mass. 02139, USA |
| |
Abstract: | Let e1, e′1, e2, e′2, …, en, e′n 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, e′j 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 等数据库收录! |
|