安全渡河问题的图解新法

针对安全渡河这一经典问题,引入图论方法,提出了一种新的图论解法.该方法将顶点设计为由"人"、"狼"、"羊"、"白菜"组成的四元组,元组中的每个元素取值可为"此岸"、"船上"、"彼岸".然后将实际模型转换为图结构,最后通过路径搜索获得问题的解.该方法有利于分析问题域的解空间,获得一般解、随机解和最优解等多种解.该方法体现了从实际模型到理论模型的转变过程,为如何运用图论来解决实际问题提供了方法借鉴.     

三维空间中多飞行器的寻迹编队控制

研究了三维空间中动力学模型描述的多飞行器在一组给定平面简单闭曲线上的寻迹编队控制问题,其中智能体的动态和给定轨道都是在固定直角坐标系下描述的.首先,通过管状邻域定理扩展平面轨道函数法,设计寻迹控制律,并用不变性原理证明了寻迹子系统的稳定性.接着,根据轨道函数与弧长函数的关系来设计编队控制律,使得有向通信连接下的多飞行器沿着各自给定的轨道编队飞行,并且利用图论证明,当通信拓扑对应的有向图具有全局可达点时,设计的寻迹编队控制系统是渐进稳定的.最后,对5架飞行器的寻迹编队飞行进行了仿真,仿真结果证明了该方法的有效性.这种寻迹编队控制律可以应用于大范围区域的信息优化采集.     

水电站工程施工供风管网优化分析

在水电站工程施工中,常遇到施工用风管路优化布置问题,本文应用图论方法建立管网生成树模型并求解,并在工程实践中得到验证.因此,图论方法可以比常规经验类比法能更好地为水电站施工提供科学参考依据.     

基于图论的网络鲁棒性增强算法

针对网络节点抗漏洞攻击能力弱、网络鲁棒性差的情况,提出一种基于图论的鲁棒性增强算法.首先介绍基于图论和多样性的网络鲁棒性策略,提出节点相关度的概念、分类描述及量化指标;其次分析多样性对各种漏洞攻击的作用.对采用该算法生成的一种30个节点、4种着色方案的图进行详细分析,对由本算法生成的六种图的统计特征进行归纳.实例表明,依照该算法构建的网络是一种较均匀的网络,这种网络能有效增强节点的抗漏洞攻击能力,阻断各种可能的漏洞攻击在节点之间的渗透和传播,减少相继故障,避免雪崩效应,具有较强的鲁棒性.     

猜球模型与算法

主要讨论猜球问题的模型建立和算法，为计算机应用于逻辑推理提供了一个素材。     

有向网络的最小流问题及其分枝定界解法

在以人为运动主体的交通网络中，堵塞是经济发生的现象。本文研究的网络最小流是指网络中发生最严重堵塞状态时通过网络的最大流量，它是设计和运行效能网络，特别是紧急疏散网络的参数。     

图的双罗马控制数的Nordhaus-Gaddum不等式

基于不同的应用背景,研究者提出了图的各种不同的控制参数。文章研究了图的控制理论中的双罗马控制问题。利用分类讨论法给出了双罗马控制数的一个Nordhaus-Gaddum不等式,推广了Jafari Rad和Rahbani的结果。     

一类基于模糊图论的费用与时间最优化问题的模型

在寻求工程实施的最小时间和费用等最优化方案时,构造了多因素隶属度PERT图和隶属函数模型,并运用模糊约束量来解决带最小化时间因素的最小费用流问题.     

一种基于图论的LDPC码构造算法的研究

在对低密度奇偶校验(LDPC)码进行分析的基础上,提出了一种基于图论的构造算法.该算法从对LDPC码的校验矩阵进行图论分析入手,分析了组成校验矩阵中的圈的校验点之间的关系,得出了由这些校验点对应的结构图是彼此同构的欧拉图的定理,利用这个定理以及根据定理得到的性质,可以通过构造一个辅助的校验点结构图的邻接矩阵,渐进地生成LDPC码的校验矩阵,在生成的过程中避免短长度圈的出现.仿真实验表明提出的算法对中短码长的LDPC码构造具有良好的性能.     

最短路径问题的解答图算法

本文给出最短路径问题的一种算法——解答图算法。它是一种十分有效的算法。对于边的数目为n×(n-1)的图(n为图的顶点数),本算法具有与Dijkstra算法同样的性能。而对于边稀疏的图,本算法在时间和空间两方面都优于Dijkstra算法,与Dijkstra算法阳比较,图的边数越少,本算法所需的存贮空间也越少,而其执行速度却越高。文中分析了时间和空间的复杂件,并给出几个实际结果。