Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is b...Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is binary if and only if for any two distinct hyper-planes H1 and H2, if H1H2S ,and H1 and H2 are modular pair, then S-(H1H2) is a hyperplande .And a necessary and sufficient condition for a binary matroid to have a k-circuit is obtained.展开更多
The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation...The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation is used for the vertices of G and the bases of M. Suppose that｜V（GI（M））｜ =n and k1＋k2＋…＋kp=n, where ki is an integer, i=1, 2,…, p. In this paper, we prove that there is a partition of V（GI（M）） into p parts V1 , V2,…, Vp such that ｜Vi｜ =ki and the subgraph Hi induced by Vi contains a ki-cycle when ki ≥3, Hi is isomorphic to K2 when ki =2 and Hi is a single point when ki =1.展开更多
Let M be a matroid defined on a finite set E and L?⊂?E?. L is locked in M if??and ?are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the lo...Let M be a matroid defined on a finite set E and L?⊂?E?. L is locked in M if??and ?are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the locked subsets. We deduce that finding the maximum-weight basis of M is a polynomial time problem for matroids with a polynomial number of locked subsets. This class of matroids is closed under 2-sums and contains the class of uniform matroids, the Vámos matroid and all the excluded minors of 2-sums of uniform matroids. We deduce also a matroid oracle for testing uniformity of matroids after one call of this oracle.展开更多
In this paper, we further study the connections between linear network error correction codes and representable matroids. We extend the concept of matroidal network introduced by Dougherty et al. to a generalized case...In this paper, we further study the connections between linear network error correction codes and representable matroids. We extend the concept of matroidal network introduced by Dougherty et al. to a generalized case when errors occur in multi- ple channels. Importantly, we show the necessary and sufficient conditions on the existence of linear network error correction mul- ticast/broadcast/dispersion maximum distance separable （MDS） code on a matroidal error correction network.展开更多
Covering-based rough sets,as a technique of granular computing,can be a useful tool for dealing with inexact,uncertain or vague knowledge in information systems.Matroids generalize linear independence in vector spaces...Covering-based rough sets,as a technique of granular computing,can be a useful tool for dealing with inexact,uncertain or vague knowledge in information systems.Matroids generalize linear independence in vector spaces,graph theory and provide well established platforms for greedy algorithm design.In this paper,we construct three types of matroidal structures of covering-based rough sets.Moreover,through these three types of matroids,we study the relationships among these matroids induced by six types of covering-based upper approximation operators.First,we construct three families of sets by indiscernible neighborhoods,neighborhoods and close friends,respectively.Moreover,we prove that they satisfy independent set axioms of matroids.In this way,three types of matroidal structures of covering-based rough sets are constructed.Secondly,we study some characteristics of the three types of matroid,such as dependent sets,circuits,rank function and closure.Finally,by comparing independent sets,we study relationships among these matroids induced by six types of covering-based upper approximation operators.展开更多
In this paper, we prove an analogous to a result of Erdös and Rényi and of Kelly and Oxley. We also show that there are several properties of k-balanced matroids for which there exists a threshold function.
In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an appro...In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms-the modified Edmonds' matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given.展开更多
Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
文摘Aim To research new characterization and circuit property of binary matroid. Methods Constract the modular pairs of hyperplanes of a a matroid. Results and Conclusion It is proved that a matroid M on finite set S is binary if and only if for any two distinct hyper-planes H1 and H2, if H1H2S ,and H1 and H2 are modular pair, then S-(H1H2) is a hyperplande .And a necessary and sufficient condition for a binary matroid to have a k-circuit is obtained.
基金Supported by the National Natural Science Foundation of China(31601209)the Natural Science Foundation of Hubei Province(2017CFB398)
文摘The intersection graph of bases of a matroid M=（E, B） is a graph G=GI（M） with vertex set V（G） and edge set E（G） such that V（G）=B（M） and E（G）={BB′：｜B∩B′｜ ≠0, B, B′∈B（M）, where the same notation is used for the vertices of G and the bases of M. Suppose that｜V（GI（M））｜ =n and k1＋k2＋…＋kp=n, where ki is an integer, i=1, 2,…, p. In this paper, we prove that there is a partition of V（GI（M）） into p parts V1 , V2,…, Vp such that ｜Vi｜ =ki and the subgraph Hi induced by Vi contains a ki-cycle when ki ≥3, Hi is isomorphic to K2 when ki =2 and Hi is a single point when ki =1.
文摘Let M be a matroid defined on a finite set E and L?⊂?E?. L is locked in M if??and ?are 2-connected, and . In this paper, we prove that the nontrivial facets of the bases polytope of M are described by the locked subsets. We deduce that finding the maximum-weight basis of M is a polynomial time problem for matroids with a polynomial number of locked subsets. This class of matroids is closed under 2-sums and contains the class of uniform matroids, the Vámos matroid and all the excluded minors of 2-sums of uniform matroids. We deduce also a matroid oracle for testing uniformity of matroids after one call of this oracle.
基金Supported by the National Natural Science Foundation of China(6127117461272492)
文摘In this paper, we further study the connections between linear network error correction codes and representable matroids. We extend the concept of matroidal network introduced by Dougherty et al. to a generalized case when errors occur in multi- ple channels. Importantly, we show the necessary and sufficient conditions on the existence of linear network error correction mul- ticast/broadcast/dispersion maximum distance separable （MDS） code on a matroidal error correction network.
基金Supported by the Research Foundation for Middle-aged and Young Scientist of Fujian Province(Grant No.JAT170731)
文摘Covering-based rough sets,as a technique of granular computing,can be a useful tool for dealing with inexact,uncertain or vague knowledge in information systems.Matroids generalize linear independence in vector spaces,graph theory and provide well established platforms for greedy algorithm design.In this paper,we construct three types of matroidal structures of covering-based rough sets.Moreover,through these three types of matroids,we study the relationships among these matroids induced by six types of covering-based upper approximation operators.First,we construct three families of sets by indiscernible neighborhoods,neighborhoods and close friends,respectively.Moreover,we prove that they satisfy independent set axioms of matroids.In this way,three types of matroidal structures of covering-based rough sets are constructed.Secondly,we study some characteristics of the three types of matroid,such as dependent sets,circuits,rank function and closure.Finally,by comparing independent sets,we study relationships among these matroids induced by six types of covering-based upper approximation operators.
文摘In this paper, we prove an analogous to a result of Erdös and Rényi and of Kelly and Oxley. We also show that there are several properties of k-balanced matroids for which there exists a threshold function.
基金Project (No. 10671177) supported by the National Natural Science Foundation of China
文摘In this paper, we consider the set partitioning problem with matroid constraint, which is a generation of the k-partitioning problem. The objective is to minimize the weight of the heaviest subset. We present an approximation algorithm, which consists of two sub-algorithms-the modified Edmonds' matroid partitioning algorithm and the exchange algorithm, for the problem. An estimation of the worst ratio for the algorithm is given.
文摘Let G be a simple graph and T={S :S is extreme in G}. If M(V(G), T) is a matroid, then G is called an extreme matroid graph. In this paper, we study the properties of extreme matroid graph.
