基于覆盖粗糙集的网络拓扑图中最小顶点覆盖问题的研究

As an important generalization of the classical rough set, covering rough set model has theoretical significance and valuable applications in the research fileds such as information sciences and management sciences. The research of the internet topology has an important theory significance for the development and application of the internet. The main objective of the project is to study the minimum vertex cover in internet topology by using the tool of covering roug sets. This project includes the following contents: (1) A covering approximation space will be established in the internet topology, the covering approximation operators and their properties will be also investigated. (2) The theory of reduction in the covering approximation space will be studied furthermore, and the relationship between the reduction of covering rough sets and the the minimum vertex cover in internet topology will be established. (3) For the dynamic and mass internet topology, approaches to the minimum vertex cover based on covering rouhg sets will be explored. The research of this project is the hot research topics of the fileds of information and mathmatics. The resolving of these problems will not only have theoretical significance to uncertainty theory, and will also be of application prospect to the research fileds such as mathmatics, information sciences and management sciences.

覆盖粗糙集模型是粗糙集模型的一种重要推广形式，在信息科学与管理科学领域中具有重要的理论意义和应用价值。网络拓扑图的研究对于网络的应用与发展具有重要的意义。本课题利用覆盖粗糙集的方法研究网络拓扑图中的最小顶点覆盖问题。主要研究内容包括：（1）在网络拓扑图上建立相应的覆盖近似空间，引入适当的上、下覆盖近似算子，并讨论相关的性质。（2）进一步研究该覆盖近似空间的约简理论，并建立覆盖粗糙集约简同网络拓扑图中最小顶点覆盖问题之间的联系。（3）考虑到网络拓扑图自身的复杂性和多变性，研究针对动态和海量数据的基于覆盖粗糙集方法的最小顶点覆盖算法。本课题所涉及的研究内容是信息与数学领域的热点问题，解决这些问题不仅对不确定性理论本身具有重要的理论价值，而且对数学、信息科学和管理等领域的实际问题有广泛的应用前景。

网络拓扑图的研究对于网络的应用与发展具有重要的意义。本课题利用覆盖粗糙集的方法研究网络拓扑图中的最小顶点覆盖问题。主要通过构造信息系统，在网络拓扑图上建立相应的覆盖近似空间。研究了该覆盖近似空间相关的性质，引入相关的近似算子。进一步探讨了该覆盖近似空间的属性约简等问题，同时也研究了网络拓扑图的一些理论性质等。对于给定的网络拓扑图，通过构造诱导的信息系统，把网络拓扑图上的顶点覆盖问题转化为粗糙集上的属性约简问题，证明了这两者之间是等价的。利用前面的理论成果，提出一种基于信息熵的最小顶点覆盖算法，并验证了该算法的可行性和有效性。同时，把网络拓扑图的顶点覆盖问题拓展到更一般的集合覆盖问题上，把粗糙集的约简问题应用到集合覆盖问题上，给出基于粗糙集方法的另外一种集合覆盖算法。最后，利用粗糙集带决策属性的加速约简方法，给出了网络拓扑图顶点覆盖问题的加速算法。课题组还进一步探讨了利用网络拓扑图顶点覆盖问题的方法研究粗糙集属性约简问题。在有影响的杂志上发表了56篇论文，多次参加各种学术会议，并被邀请做了三场大会报告。