The Research And Application Of Graph Theory In Uncertain Network Planning Is A Circle Problem

With the development of society,network programming and graph theory are widely used in various fields.A number of practical problems can be abstracted as network programming problems,and the circle problem is its the basic problem.In this thesis,these knowledge and methods,such as graph theory,uncertainty theory,network programming and optimality theory,are used to study circle problems in uncertain network programming.Firstly,on the basis of uncertain graph theory,the general concept of spanning tree of uncertain graph,its matrix representation method and related theorems are generalized,and based on this,the general concept of uncertain circle,matrix representation method and its property theorem are proposed.And the calculation methods of cycles and cyclical edge-connectivity based on Prim algorithm are designed.Then,according to uncertainty theory and network programming,two kinds of circle problem model based on measure matrix are established,and their solving algorithms are designed.Finally,the theory and method of circle problem proposed are used to plan their best route of tourism route planning.And the planning results show that the theory and method presented are correct and reasonable.The main work is as follows:(1)Studying the definition and related theorems and matrix of spanning tree of uncertain graph.On the basis of edge-structured uncertain graph and point-structured uncertain graph,firstly,the definitions of spanning trees of edge-structured uncertain graph and point-structured uncertain graph are proposed and proved respectively.Its definitions are used to discriminate spanning trees of uncertain graph.Then,by analogizing the measure matrix representation of uncertain graph,the measure matrix of the spanning tree of uncertain graph is proposed,and it is used to unify edge-structured uncertain graphs and point-structured uncertain graphs.Finally,the spanning tree measure matrices of these two kinds of uncertain graphs are analyzed and compared.(2)Studying the related concepts and theorems and matrix of circle of uncertain graph.Based on the proposed spanning tree of uncertain graphs,firstly,analogying the calculation method of the number of basic cycles and cycles of certain graph,the theorem of calculating the number of basic cycles and cycles of uncertain graphs is proposed and proved.Then,analogying the complete circle matrix representation,a measure matrix of the circles of uncertain graphs is proposed,which can provide the information of this circles intuitively.Secondly,based on the circle measure matrix,the definitions of the number of edges of rings and connectivity of uncertain graphs are given respectively.Finally,based on the idea of Prim algorithm and the greedy criterion of the order priority of the spanning tree of uncertain graph,an algorithm for calculating the connectivity of uncertain graph and rings is designed,and a numerical example is given to verify the rationality of the algorithm.(3)Studying circle problem model and algorithms in uncertain network planning based on measure matrix.Firstly,analogying the traditional modeling ideas of Euler and Hamilton cycles,the Euler and Hamilton cycles models in uncertain network planning based on measure matrix are established.Then,the problem of Euler and Hamilton cycles with uncertain graph structure is transformed into the problem of Euler and Hamilton cycles with certain graph structure by using probability theory.Finally,based on Edmonds algorithm and two-sided successive modification method,the solving algorithms of Euler circle model and Hamilton circle model in uncertain network planning are designed respectively.(4)Studying an example of tourism route planning in uncertain network planning.Firstly,the location of scenic spots is regarded as the vertex of the network graph,and the ratio of actual driving time to acceptable average driving time is regarded as the relationship between two vertices with edges.So the tourism route planning problem can be abstracted as the circle problem in the uncertain network.Then,based on the uncertainty of tourists' preferences,a computational model of uncertain measures of vertices and edges in uncertain network is established.The uncertainties of vertex existence and edge existence are depicted by using the actual spent time and the acceptable time spent respectively,the actual driving time and the acceptable driving time.Finally,the best tourism route planning model is constructed,and the best tourism route is obtained by using the method in(3).The results show that the method proposed in this paper is reasonable.