Independent Set Index In Uncertain Graph

In the practical application of graph theory,with the increase of complex systems,uncertain factors,such as inaccurate expert data model,are often encountered.After probability theory and measure theory,Liu established the uncertainty theory in 2007and applied the uncertainty theory to the network in 2010.In 2010,Han and Peng studied the maximum flow problem on the uncertain network.In 2011,Peng and Li established the uncertainty model on the minimum spanning tree problem.Zhang and Peng studied the postman problem on uncertain networks.With the introduction and application of uncertain graph,the theory of uncertainty is more and more applied to graph theory,which leads to the study of uncertain graph.In 2013,Gao and Gao gave the definition of uncertain graphs for the first time and studied the tree index and circle index of uncertain graphs.Later,Zhang and Peng studied the Euler circle and Hamiltonian circle of uncertain graphs.In 2014,Yuan studied the distribution function of the diameter of uncertain graphs.In 2017,Chen studied the coloring problem of uncertain graphs.In an uncertain graph,the existence of edges is unpredictable,and edges can be assigned to describe these uncertainties.This makes the original field of graph theory have a further expansion,such as the connectivity index of uncertain graph,uncertain graph coloring problem and so on.The maximal independent set of uncertain graphs is essentially an uncertain variable.Under the operating rules of the uncertain theory,this paper studies the index of independent set of uncertain graphs,aiming to combine the independent set with the uncertain theory.To this end,a set of independent based on uncertain graph index is presented the first time in this article,the focus of this article is to give a kind of uncertain graph independent set index calculation algorithm,we first discuss the degree of the set independently in uncertain graph,and give the definition of independent set index.Also,we point out the equivalence relation of the independent set in an uncertain graph G and the clique in its complement G~*,And some properties are studied.An efficient algorithm is designed based on the algorithm of searching complete subgraphs.In addition,some numerical examples show the effectiveness and practicability of the algorithm.Finally,this paper also puts forward the prospect of the future work.