Research On Uncertain Digraph And Network Optimization Problem

In classical graph theory, the vertices and the edges are all deterministic, ei-ther existing or not. However, as the system becomes more complex, indeterminacy factors may appear in graphs in practical applications. When indeterminacy fac-tor comes from expert's empirical estimation, it is not suitable to employ random variable to describe this kind of indeterminacy factor. As a result, it has a broad background and significance in theory and practice to study uncertain digraphs and uncertain network optimization problems.In theoretical aspect, this dissertation investigates uncertain digraph. Firstly, it proposes the concept of uncertain digraph. Then it investigates the connectivity of uncertain digraph, and proposes the concepts of local connectivity and strong connectivity. The methods to calculate local connectivity and strong connectivity are also given. Next, this dissertation proposes the concept of vertex degree of uncertain digraph, and then it investigates some properties of regularity of uncertain digraph. Furthermore, the definition of complement of an uncertain digraph is given and some properties of uncertain self-complementary digraphs are studied. In addition, it also studies some other operations on uncertain digraphs such as union, join, and Cartesian product.In practical aspect, this dissertation investigates a typical class of optimization problem in uncertain network. Firstly, the definition of uncertain network is mod-ified based on digraph. Briefly, a digraph with uncertain arc weights produces an uncertain network. Secondly, it investigates uncertain minimum cost flow problem, which is a typical class of optimization problem in uncertain network. As a result, a mean-variance-chance model for the problem is proposed, the crisp equivalence of the model is investigated, and some properties of the model are analyzed. In addi-tion, a hybrid intelligent algorithm for solving the proposed model in general cases is presented. At last, some numerical examples are presented to show the applications of the model and algorithm.The contributions of this dissertation are:1. It proposes a definition of uncertain digraph, and gives methods to calculate the connectivity of uncertain digraph. 2. It investigates some properties of regularity of uncertain digraph. It also introduces some operations on uncertain digraphs such as complement, union, join, and Cartesian product.3. It modifies the concept of uncertain network based on digraph, and inves-tigates the minimum cost flow problem on uncertain network. A mean-variance-chance model for the problem is proposed. In addition, an algorithm for the model is introduced.