一种新的基于递归分解的图可达性查询算法

针对现实中许多超大规模图可达性查询的问题,提出了一种新的基于递归分解的算法,即将原图递归分解成一系列生成树和剩余图两类子图,并通过分别查询这两类子图来减少查询开销.相比于区间标记、链分解、2-hop标签和路径树等传统算法,该算法不仅空间开销更小,且时间复杂度更低.仿真实验表明,该算法对处理大规模有向图可达性问题上存储规模更小且查询效率更高.     

有向图中环路判定算法研究

在分析了传统环路判定算法的基础上,提出了一种更高效的环路判定算法,以获得更高效的时间复杂度。     

(V,R)-语言

V是一个字母表。FV是V上的一个自由半群,R是FV的一个子集。首先,提出了(V,R)-半群的概念,证明了图半群和有向图半群都是(V,R)-半群。其次,提出了超图半群的概念,证明了超图半群是(V,R)-半群,超图半群把超图理论和自由半群理论联系起来。以此为基础,提出了(V,R)-语言和超图语言两个概念。超图语言把超图理论和形式语言理论联系起来。进而,证明了超图语言、无向图语言和有向图语言都是特殊的(V,R)-语言。第三,证明了无向图语言和有向图语言都是正则语言。这就回答了文献"无向图语言"和"有向图语言"中提出的开问题。(V,R)-半群和(V,R)-语言是研究自由半群和形式语言的新理论和新方法。     

某类定号有向图基的界

对某类带有3个圈的本原不可幂的定号有向图进行了研究,通过分析此图的特点,给出了符号模式矩阵、有向图和定号有向图的定义,介绍了指数的界和基的界的有关算法,再综合运用指数、途径对、数和异圈对的相关性质,得到了该类定号有向图的基的界和在特殊情形下的基.     

围长为2的奇数阶本原极小强连通有向图的1-指数集

研究了围长为2的n阶本原极小强连通有向图的1-指数集,证明了当n(≥5)为奇数时,En(1)={4,5,6,7,…,2n-5},无缺数段。     

一类特殊本原不可幂定号有向图的广义基

考虑了一类含有三个n—2圈和一个n圈本原不可幂定号有向图的广义基,通过分析图中是否存在寻求的途径及SSSD途径对,运用本原不可幂定号有向图的一些定义和性质,给出了此类图的广义本原指数及广义基.     

基于有向图的静止气象卫星故障检测模型

为解决基于卫星单个遥测值超限进行报警的方法会引起故障的误报和漏报这一问题,提出一种基于有向图的静止气象卫星故障检测模型。定义组合条件报警故障知识规则的描述方法和故障知识库,能够同时对卫星多个通道的遥测值进行综合分析与诊断,提高故障的诊断效率;基于有向图实施卫星故障的自动检测,省去关联故障的判别工作,减少冗余告警,提高故障检测的正确性。实际业务运行结果验证了该模型的可行性与有效性。     

基于有向图的足球视频中球员分类算法

基于传统的直方图球员分类方法由于缺乏描述图像颜色的空间信息而造成分类误差,而且该方法需要先验的模板信息。为此,本文提出一种基于有向图的足球球员的分类方法。首先,利用HSV模型中主颜色方法提取候选球员,并利用等面积矩形划分策略对图像进行分块;其次,对子块的HSV颜色空间进行量化,并将统计直方图作为颜色特征,然后通过颜色特征计算图像之间的距离,并利用距离矩阵生成对应有向图;最后,通过对有向图的顶点分类实现球员的分类。实验结果表明,本文提出的方法能够在没有先验模板信息的条件下,能够有效地解决处在分类边界上的球员分类问题,获得98.23%的分类正确率,与传统方法相比,具有更好的分类效果。     

针对有向图的局部扩展的重叠社区发现算法

当前社区发现算法主要是针对无向图研究社区结构,但在实际复杂网络中,链接关系时常表现出非对称性或方向性,比如Twitter的用户关注关系,文献网络的引 用关系,网页之间的超链接关系等应用网络。因此,本文依据信息在复杂网络中的传播规律和流动方向性,提出了k-Path共社区邻近相似性概念及计算方法,用于衡量结点在同一社区的相似性程度,并给出了把有向图转换为带方向权值的无向图的方法。基于带权无向图提出了一种从局部扩展来探测社区的重叠社区发现算法(Local and wave-like extension algorithm of detecting overlapping community, LWS-OCD)。在真实数据集上的实验表明,共社区邻近相似性概念实现了有向到无向的合理转换,而且提高了社区结点的聚集效果,LWS-OCD算法能够有效地发现带权无向图中的重叠社区。     

非平衡拓扑结构的多智能体网络系统一致性协议

针对多智能体网络系统,本文分别研究了非平衡拓扑结构的多智能体连续状态和离散状态下的一致性协议.首先提出了能使用有向图表示的多智能体网络系统的拓扑结构,并根据该拓扑结构建立了网络系统的1阶数学模型和提出了多智能体网络系统一致收敛准则.对于多智能体网络连续系统,该系统的一致平衡点最终收敛于初始状态的凸组合,本文最终确定了非平衡拓扑结构的一致平衡点.如果多智能体网络系统的拓扑结构没有改变,在离散状态下系统的一致平衡点仍收敛于初始状态的凸组合,并且离散状态下系统的一致平衡点与连续状态下系统的一致平衡点相等.最后采用8个智能体组成的网络拓扑进行计算机仿真,验证理论的正确性.