不确定图与不确定网络

Uncertain Graph and Uncertain Network

作者: 专业:数学 导师:刘宝碇 年度:2013 学位:博士 

关键词
不确定理论 不确定图 不确定网络

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

不确定图与不确定网络

摘要3-4
Abstract4
主要符号对照表7-8
第1章 引言8-13
    1.1 选题背景及意义8-10
    1.2 研究现状10-11
    1.3 本文的结构安排11-13
第2章 预备知识13-26
    2.1 不确定理论13-21
        2.1.1 不确定测度、不确定变量及不确定分布13-17
        2.1.2 不确定变量的性质17-21
    2.2 图21-24
    2.3 网络24-26
第3章 不确定图论的基本概念和基本定理26-34
    3.1 不确定图及相关概念26-28
    3.2 基本定理28-34
第4章 不确定图的边数、边连通度和直径34-53
    4.1 不确定图的边数34-36
    4.2 不确定图的连通指数36-39
    4.3 不确定图的边连通度39-46
    4.4 不确定图的直径46-49
    4.5 不确定图的半径和Wiener指数49-51
    4.6 含有不确定顶点的图51-53
第5章 不确定网络优化53-65
    5.1 不确定网络53-54
    5.2 不确定网络中的最短路径问题54-65
        5.2.1 问题描述54-56
        5.2.2 不确定变量fSP的分布56-58
        5.2.3 α-最短路和最大测度最短路58-61
        5.2.4 例子61-65
第6章 结论65-67
    6.1 论文的主要工作65
    6.2 论文的创新点65-66
    6.3 今后研究的展望66-67
参考文献67-72
致谢72-74
个人简历、在学期间发表的学术论文与研究成果74


本文地址:

上一篇:大规模稀疏线性系统的稀疏近似逆预处理技术
下一篇:量子群典范基的参数化和Hall代数范畴化

分享到: 分享不确定图与不确定网络到腾讯微博           收藏
发表网-不确定图与不确定网络-在线咨询