基于图论的建筑电气设备连接逻辑自动生成模型

为了更好地描述建筑电气设备之间的连接关系,设计了基于图论的建筑电气设备连接逻辑自动生成模型。依据图论原理和建筑电气设备的共通性,以设备和配件连接关系的交叉点作为连接器,以连接关系的边为无向拓扑图的边,形成电气设备拓扑图并以邻接矩阵形式存储,利用Dijkstra算法计算设备最短连接路径,完成电气设备连接逻辑自动生成。实例结果表明:该模型获取的阀门、泵和机组之间的逻辑关系清晰明了,且当建筑配件数量为2000个时,其逻辑提取耗时仅为9.23 s,逻辑提取能力强,能有效获取设备连接最短路径,清晰描述电气设备之间逻辑关系。

六柱实心鲁班锁设计方法研究

现有研究无法系统性地设计出具有不同内部结构的鲁班锁,因此提出一种新的六柱实心鲁班锁设计方法。首先对六柱鲁班锁结构进行了数字化描述,以坐标矩阵表示鲁班锁的三维模型。将鲁班锁划分为内部和外部区域,并对内部区域进行排列组合,根据无向图的连通性判断柱杆连通性,在保证每个柱杆连通的情况下得到新的装配结构。在MATLAB中虚拟拆卸装配结构,将可全部拆卸的装配结构输出对应的坐标矩阵,若柱杆发生干涉无法全部拆出,则重新构造装配结构继续拆卸,直至柱杆全部拆卸并输出坐标矩阵。最后根据坐标矩阵,还原三维模型作为新型鲁班锁。研究结果表明,随着程序运行次数的增加,有望得到设计空间中更多可行解。此方法为鲁班锁结构的创新设计开辟了新途径。

对数空间可构造的无向图遍历序列

研究了为无向连通子图设计环状遍历序列(TSC)的空间复杂性问题。通过定义对数空间的Cook归约,分析了TSC问题与无向图连接性问题及通用遍历序列构造问题的关系,证明了TSC问题以及无向图遍历问题是对数空间可解的,并给出了一个TSC一般性构造方法。最后还提出了一个更有效的针对树状图的TSC构造算法。

基于事件触发机制的多智能体网络平均一致性研究

研究了事件触发机制下具有固定和切换拓扑结构的多智能体网络的平均一致性问题。为了有效降低多智能体一致性控制协议的更新次数,提出了仅依赖于各智能体及其邻居节点信息的分布式事件触发机制;为了使多智能体网络渐近收敛至初始平均状态,提出了基于事件触发机制的多智能体平均一致性协议;然后,建立了事件触发机制下的闭环系统模型,并分别获得了固定和切换拓扑结构下多智能体网络平均一致收敛的充分条件。仿真表明,基于事件触发机制的平均一致性协议保证了多智能体网络的平均一致性,并且分布式事件触发机制有效降低了多智能体一致性协议更新次数。

Prim算法在架设通信网络系统中的应用

通信网络系统架设属于典型的图论优化问题,针对通信网络系统的特点,抽象问题,简化模型,以通信网络系统架设费用最小为优化目标,应用Prim算法进行通信网络系统架设模型研究。首先简述了七城市之间架设通信网络系统问题,然后应用数学建模知识对隐含在该问题中的图论模型进行抽象研究,进而构造问题的数学模型,最后应用Prim算法设计了该通信网络系统架设的实现流程及相应代码的编写。程序执行结果表明:准确构建了问题的数学模型及应用Prim算法正确求解了该数学模型;并且权值因子的可变性使得该程序具有较强的通用性,易于在实际中使用。

节点不完全可靠无向网络k-端可靠度计算

可靠性是保障网络系统正常运行的必要条件,k-端可靠性问题是网络可靠性的最一般问题。通过对已有的计算2-端可靠度的方法进行扩展和改进,提出了一种计算节点不可靠无向网络k-端可靠度的方法。先将图的边定义为链路及其端点,然后通过矩阵变换运算,得到不相交的k-端路径,在此基础上,利用条件概率对k-端路径的概率进行求解以得到网络k-端可靠度。该方法不仅可用于分析节点和链路不可靠的情形,还可用于分析节点和节点间存在多条链路的情况。最后在网络链路和节点的工作寿命服从负指数分布时计算了示例网络的k-端可靠度,以说明本方法。

复杂无向网络连通性的一种高效判定算法

通信网络的拓扑结构连通性是多智能体系统一致性控制或编队控制等的理论前提.以往,各种多智能体系统一致性控制或编队控制方面的文献仅侧重于控制协议、智能体动力学模型和控制律设计,而缺乏对多智能体通信网络拓扑结构的连通性研究.网络连通性高效判定算法不仅是大规模多智能体系统一致性控制或编队控制的保证,而且在图论、现代移动通信、计算机与交通等各种网络中有着重要和广泛的应用.针对复杂无向网络的连通性问题,本文给出了一种新的高效判定算法、以及该算法的时间复杂度和空间复杂度的上界.该算法具有非常低的时间复杂度和空间复杂度,且便于计算机实现,因而具有重要的理论意义和广泛的实用价值.

从节点度数生成无向简单连通图

许多现实问题可以抽象成无向简单连通图的生成问题。为了从节点的度数序列得到所有可能的无向简单连通图,针对度数序列设计了适合用计算机实现的去点回溯算法,证明了算法的正确性,通过每一步去点回溯后的变化矩阵,得到生成无向简单连通图所需的邻接矩阵,并最终用计算机实现了该算法,解决了节点度数已知时无向简单连通图的生成问题。

Kautz图的限制边连通度

限制边连通度是对传统边连通度的推广 ,而且是计算机互连网络容错性的一个重要度量 .本文考虑两类重要的网络模型———Kautz有向图K(d ,n)和Kautz无向图UK(d ,n)的限制边连通度λ′,并得到如下结果 :除了λ′(K( 2 ,1) )不存在外 ,均有λ′(K(d ,n) ) =2d-2 ;当d≥ 3 ,n≥ 3时 ,4d-5≤λ′(UK(d ,n) ) ≤ 4d -4 .

基于相异度度量的图聚类方法

聚类是分析和探测数据的重要方法,而图聚类则是一种非常重要的特征模式聚类的变体。以无向非加权连通图为研究对象,提出了一种基于节点间相异度度量的凝聚层次聚类方法。实验表明该算法简单有效,适合一般图的聚类。

基于VB的最小生成树KRUSKAL算法的实现

对求解加权连通无向图最小生成树的KRUSKAL算法进行了探讨,并用VB实现,同时以读取文件的方法输入图,弥补了利用面向过程的程序设计语言在求解最小生成树时输入数据的复杂性。通过可视化的形式显示无向图和最小生成树,使结果直观且容易理解。

基于图的半监督学习的遮挡边界检测方法

提出了一种基于图的半监督学习检测深度图像中遮挡边界的方法。该方法首先获取已标记的像素点和待检测深度图像中的像素点作为顶点构建连通无向图，其次提取无向图中各像素点的最大深度差特征和八邻域有效深度差之和特征组成特征向量，根据像素点的特征向量计算无向图中顶点之间的相似性并将该相似性作为无向图中对应边的权值，然后根据图的半监督学习思想判断无向图中待检测像素点是否为遮挡边界点，最后可视化遮挡边界点得到深度图像中的遮挡边界。实验结果表明，所提方法尽管只需少量的标记样本，但在准确性上却同已有基于监督学习的方法相当。

无向Kautz图的超级限制边连通性(英文)

限制边连通度作为边连通度的推广,是计算机互连网络可靠性的一个重要度量.Superλ-′是比限制边连通度更精确的一个网络可靠性指标.一个图是Superλ-′的,如果它的任一最小限制边割都孤立一条有最小边度的边.本文考虑一类重要的网络模型-无向K autz图UK(d,n)的限制边连通度λ,′证明了当d 3,n 2时,λ(′UK(d,n))=4d-4,并进一步指出此时的UK(d,n)是Superλ-′的.

论图的坚韧度（Ⅰ）──基本理论

本文首先指出坚韧度τ（Ｇ）是可以用来刻划图的连通性，因而能广泛地应用于通讯网络可靠性等有关领域的研究。进而，研究了坚韧度的自身特性，诸如取值范围、存在性问题、计数问题以及计算问题等。

无向 Kautz 图的限制性连通度和限制性容错直径

证明直径为ｌ且最小和最大度分别为３和４的无向Ｋａｕｔｚ图具有限制性连通度４，且其限制性容错直径至多ｌ＋１４．

离散数学中的闭包概念及应用

基于闭包的放大和最小性特点来处理离散数学中相关概念,梳理了离散数学中显性和隐性的一些闭包概念,如二元关系的闭包、强分图、子空间、和空间、生成子群等.试图在闭包的框架下将这些概念的教学格式化,操作过程标准化.同时,介绍了作者的教学方案和一些教学技巧,最后将关系传递闭包的思想应用到最短路径及一笔画问题等案例的算法设计中.

任意无向图的R点连通扩充

为研究以最少边集扩充一个任意无向图为R点连通图这一尚未解决的优化问题,通过将无向图点连通问题转化为有向图边连通问题,采用增广扩充的方法,提出了一个复杂度为O(|V|5)的算法．利用该算法可最优地将给定无向图中任意2点达到所要求的点连通度．它发展了K点连通最优扩充的研究,从而使图的点连通扩充的研究在应用于网络设计的可靠性设计方面更具有实际意义．

无向树图的k点连通最小扩充

解决了以最少边集扩充一个任意无向树图为k点连通图这一优化问题,提出了一个计算复杂度为D(|V|~4)的算法。为进一步研究可靠网络的计算机辅助设计打下基础。

一类排污问题在树图上的线性算法

ＭＥＧＩＤＤＯ等人证明了图搜索问题的ＮＰ完全性并给出一个树图上的算法，可在Ｏ（ｎ）时间内求解树的搜索数，在Ｏ（ｎｌｏｇ（ｎ））时间内求解树搜索方案．本文通过引入搜索方案边序表示法给出一个线性算法，可在Ｏ（ｎ）时间内同时求得树的搜索数和搜索方案．

无向简单图与无向连通图自动识别系统

近年来,图论越来越受到全世界数学界和其它科学界的广泛重视。图的理论及其在物理、化学、运筹学、计算机科学、电子学、信息论、控制论、网络理论、社会科学及经济管理等几乎所有学科领域中各方面的应用研究都迅速发展。无向图作为图论的重要组成部分,研究无向图的连通性问题具有很重要的意义。本文介绍了无向简单图与无向连通图自动识别系统的设计与实现过程。