Uncertain Graph And Uncertain Network

In classical graph theory and network optimization, the vertices and edges are de-terministic. However, in applications, because of the lack of information, the imprecisefactor has to be taken into account when modeling the graph or network. In many situa-tions, the imprecise information is given in the form of expert data. This paper employsuncertain variable to describe the imprecise information from expert’s experimental. Inthe framework of uncertainty theory, some basic problems of uncertain graph and uncer-tain network are investigated.This paper first proves an important theorem, which will be frequently used. Thenit investigates the size, edge-connectivity and diameter of uncertain graph. The size ofuncertain graph is an uncertain variable, and this paper gives its expected value and un-certainty distribution. The study of edge-connectivity is based on the conclusion of con-nectedness index. This paper gives an algorithm to calculate the uncertain measure ofedge-connectivity. The diameter of uncertain graph is also an uncertain variable, and itsuncertainty distribution is investigated by this paper.A network can be regarded as a graph with weight on edge. If the weight is anuncertain variable, an uncertain network is obtained. When solving the optimizationproblems in uncertain network, the classical algorithms can not be employed directly.This paper investigates the uncertain shortest path problem, and provides a method tosolve the optimization problems in uncertain network.The innovation of this paper includes:Proving a theorem, which simplifies the operational law of uncertain variable andis the base of many algorithms in uncertain graph;Investigating the size, edge-connectivity and diameter of uncertain graph, and giv-ing the algorithm to calculate the uncertain measure of these variable;Investigating the shortest path problem in uncertain network, giving the uncertaintydistribution of the length of shortest path, and giving the algorithm to find the mostshortest path and theα shortest path.