|
|
|
| Covering Matroid and Its Graphical Representation |
| LI Qing-Yin, LIN Zi-Qiong, ZHU William |
| Laboratory of Granular Computing, Minnan Normal University, Zhangzhou 363000 |
|
|
|
|
Abstract Matroid theory has a powerful axiomatic system, which lays a solid foundation for the combination of matroids and other theories. A matroidal structure is constructed by a covering of a universe, and the graphical representation of the matroid is studied. Using the indiscernible neighborhoods, the partition of a universe is induced by a covering of the universe. Through the partition, the matroidal structure of the covering is constructed. The set of all circuits of the matroid is represented by the covering. Finally, the matroid is proved to be a graphic matroid.
|
|
Received: 26 June 2013
|
|
|
|
|
|
[1] Hu Q H, Yu D R, Liu J F, et al. Neighborhood Rough Set Based Heterogeneous Feature Subset Selection. Information Sciences, 2008, 178(18): 3577-3594
[2] Zhu W. Topological Approaches to Covering Rough Sets. Information Sciences, 2007, 177(6): 1499-1508
[3] Zhu W. Relationship between Generalized Rough Sets Based on Binary Relation and Covering. Information Sciences, 2009, 179(3): 210-225
[4] Deng T Q, Chen Y M, Xu W L, et al. A Novel Approach to Fuzzy Rough Sets Based on a Fuzzy Covering. Information Sciences, 2007, 177(11): 2308-2326
[5] Estaji A A, Hooshmandasl M R, Davvaz B. Rough Set Theory Applied to Lattice Theory. Information Sciences, 2012, 200: 108-122
[6] Wang S P, Zhu W. Matroidal Structure of Covering-Based Rough Sets through the Upper Approximation Number. International Journal of Granular Computing, Rough Sets and Intelligent Systems, 2011, 2(2): 141-148
[7] Lawler E L. Combinatorial Optimization: Networks and Matroids. Mineola, USA: Dover Publications, 2001
[8] Edmonds J. Matroids and the Greedy Algorithm. Mathematical Programming, 1971, 1(1): 127-136
[9] Rouayheb S, Sprintson A, Georghiades C. On the Index Coding Problem and Its Relation to Network Coding and Matroid Theory. IEEE Trans on Information Theory, 2010, 56(7): 3187-3195
[10] Bonikowski Z, Bryniarski E, Wybraniec-Skardowska U. Extensions and Intentions in the Rough Set Theory. Information Sciences, 1998, 107(1/2/3/4): 149-167
[11] Lai H J. Matroid Theory. Beijing, China: Higher Education Press, 2002 (in Chinese)
(赖虹建.拟阵论.北京:高等教育出版社, 2002)
[12] Diestel R. Graph Theory. 4th Edition. Berlin, Germany: Sprin-ger-Verlag, 2010 |
|
|
|
2014, Vol. 27 
