【作者】 高原；

【导师】 刘宝碇；

【作者基本信息】 清华大学 ， 数学， 2013， 博士

【摘要】 在经典的图和网络问题中,顶点和边的信息是确定的.然而,在实际应用中,信息的不精确、甚至缺失是不可避免的.这就导致了从该问题抽象出图的模型时,必须将不精确信息反映在图中.很多情况下,不精确信息表现为专家经验数据的形式.本文借助不确定理论,以不确定变量来刻画图中来自专家经验的不精确信息,并以此展开对不确定图和不确定网络的研究.本文首先给出了不确定图的定义和相关概念,并证明了不确定图中常用的定理.接着本文从边数、边连通度和直径等基本性质展开对不确定图的研究.边数在不确定图中是一个不确定变量,本文给出了它的分布函数和期望.连通性问题是图论中最基本的问题之一.在连通指数的基础上,本文展开了对不确定图边连通度的研究,并给出了相关问题的算法.在连通性问题之后,本文研究了和距离相关的几个变量,包括直径、半径和Wiener指数.这一部分主要展开对直径的性质的讨论,推导出了直径不确定分布函数的算法.在图的边上赋予权重,就得到网络.如果所赋予的权重不是确定的数值,而是一个不确定变量,那么就得到了一个不确定网络.因为不确定变量的存在,在求解不确定网络上的优化问题时,就不能直接套用图中的经典算法.本文展开了对不确定网络中最短路径问题的研究,并以此为例,为研究不确定网络上的优化问题提供了一种思路.总体说来,本文的创新点主要有：推导出不确定图论研究中的基本定理,该定理简化了不确定变量的运算法则,并保证了后续算法的实现;首次研究了不确定图的边连通度和直径的性质,给出了求解相应不确定测度的有效算法;在不确定网络上最短路径问题中,给出了最短路径长度的分布函数,并给出了寻找α最短路和最大测度最短路的算法.更多还原

【Abstract】 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.更多还原