关于生成有向图的全部有向回路的回路向量空间法

本文提出一个由有向图的(1)有向回路基集或(2)定向回路基集,通过线性组合,生成全部有向回路的算法。文中证明了一条点数边数相等原则。根据此原则,得到一个识别有向回路的简单方法,从而使算法的计算时间与对应的无向图算法基本相同。     

基于角速度修正的变结构多模型目标跟踪算法

为提高强机动目标的跟踪精度,提出一种基于角速度估计值自适应修正的变结构多模型算法。将角速度估计应用于基于有向图切换的变结构多模型目标跟踪算法。通过引入改进的角速度估计方法,提高了角速度的估计精度。在有向图切换的基础上,实时估计角速度,并根据角速度估计值修正有向图,增强了变结构多模型目标跟踪算法的机动适应性。仿真结果表明,该方法在对强机动目标的跟踪性能上有明显提高。     

基于有向图的综合航电系统结构设计及优化方法

结构设计和优化方法关系到航电系统乃至战机可用性、扩展性和可维护性等多方面。分析系统结构设计过程, 明确设计步骤, 用于指导系统结构的构建。基于有向图理论, 提出系统结构有向图的概念, 并给出了数学描述。在此基础上, 进一步阐述了结构优化算法, 对系统结构有向图进行横向和纵向分解, 建立了一种层次化的资源关联结构, 为结构设计提供理论依据。最后, 以实例说明了该方法的有效性。     

基于有向图的电磁环境复杂度度量算法

以用频装备接收机的信噪比参数和用频网络可用性作为度量依据,定义了用频网络的4级电磁环境复杂度度量标准.在此基础上,通过将用频网络转化成有向图,提出了基于有向图的电磁环境复杂度度量算法,并以此算法为基础定义了战场电磁环境复杂度.通过计算战场电磁环境复杂度使得当前战场电磁环境对作战行动的影响程度定量化,为复杂电磁环境条件下的战场决策提供必要条件.     

求有向图中源点到各结点所有路径的一种实用算法

给出了有向图中求解源结点到各顶点之间所有路径问题的一个算法,该算法能够求出他们的所有路径,并按照路径权值的大小递增排列,在算法的实现中第一次应用邻接矩阵求解各结点的前趋以便得到各结点的路径运算顺序,然后通过邻接表的数据结构实现此算法,此算法已用C语言编制的相应程序验证了其可靠性和实用性.     

应用超图理论实现有向基本割集矩阵

本文应用超图理论提出了从有向基本割集矩阵Qf的树路子阵Qfp逐层判断其可实现性和综合出其对应有向图(G)的算法RFCMHGT。它的原理直观,计算复杂度为O(nl2),n和l为Qfp的行和列数。例2表明,Tutte条件不是Qf可实现的充分条件。     

基于有向图的工作流模型的设计与实现

文章通过定义环节节点、有向边构建了基于有向图的工作流模型,利用此模型可以直观地、清晰地表达各种业务工作过程,以解决传统工作流模型在过程表达方面的不足,并结合信息系统开发实例进行了设计和实现。     

基于ECA规则的工作流建模

将工作流模型划分为三部分：过程模型、数据模型、组织模型。通过ECA规则与有向图相结合对工作流进行过程建模，利用有向图直观地表述流程的走向，工作流引擎通过对ECA规则的解释导航流程；给出了数据模型中数据对象的形式化定义；在组织模型中对RBAC模型进行改进，解决其在细粒度权限控制上的不足。     

有向图在关系数据理论中的应用

针对关系数据理论中如闭包、最小函数依赖集的求解、BCNF的分解等算法表达相对抽象的情况,提出将图论中的有向图引入到函数依赖的表达之中,运用有向图的图像变换及算法来进行关系数据理论相关问题的处理,使得其表达、求解过程更为直观、简洁,更容易理解和接受。     

嵌入式系统中基于DAG的容错调度算法设计

首先针对任务间有依赖关系的任务,建立了有向图(DAG)任务模型;随后,采用动态关键路径调度策略BDCP(Better List Scheduling Algorithm)进行静态调度;最后是以BDCP为基础,在同步节点处添加可重叠的时间冗余,提出了FT-DAG(Fault Tolerant DAG)容错调度算法。同步节点是指DAG中那些直接前继个数大于1的节点。同步节点恢复技术具备容错、提升调试能力以及更少的容错开销。通过一个实例展现FT-DAG的调度过程,并把FT-EDFFT容错调度算法与之对比,验证所提算法的优势。     

生成有向图全部有向回路的一个有效的回路向量空间算法

本文提出一种生成有向图全部有向回路的、有效的回路向量空间算法,其中每个有向回路都由一个连支定义的基本回路(有向回路或半回路)和一组已获得的有向回路的环和产生,同时可将每个有向回路用一个选定的有向回路基集的线性组合表示。     

THE AUGMENTATION OF UNDIRECTED WEIGHTED GRAPH TO A K-EDGE-CONNECTED GRAPH

An approximation algorithm is presented for augmenting an undirected weightedgraph to a K-edge-connected graph.The algorithm is useful for designing a reliable network.     

一种求偶图的所有完备匹配算法

求给定偶图的所有完备匹配问题在LSI/VLSI的布图设计方面有着重要的应用。本文提出了一种求解这一问题的算法。(1)提出了许配树的概念并讨论了其性质;(2)证明了任意一棵许配树T(xi)对应于给定偶图的所有完备匹配的定理;(3)给出了求给定偶图的所有完备匹配的算法。本算法已在BST 386 CAD工作站上用C语言实现。运行结果证明了算法的正确性。算法已作为正在研充的VLSI积木块布图设计系统中的一个模块。     

任意无向加权图的K边连通扩充

本文研究了以最小或近似最小权值的边集扩充一个任意无向加权图为K边连通图,文中给出了一个近似算法,为网络的可靠性设计和改建提供了一个新方法。     

基于图模型的多边形自动构建算法

为了克服线拓扑造区效率低的问题,根据图模型中有向闭合环的特点,提出了一种基于图模型的鲁棒性较强的多边形构建方案.该方案首先将线数据构成图模型,并对图模型进行预处理;然后根据图模型生成环,再依据有向环的构成方向,判断有效环是洞还是壳;最后,把生成的洞分配给其对应的壳.壳的个数即为生成多边形的个数.该算法可较好地解决大规模线性数据生成区的效率问题,同时用其与混合模型,要素模型和简单要素模型进行了比较,实验中采用了四叉树索引和R树索引,都具有较高的效率,其中四叉树索引在实验中对于93664大小的线数据生成区数据,比要素模型快了5.400 s,比简单要素模型快了3.641 s.实验结果说明该算法性能优于其他的同类算法.     

非线性流水线优化中MAL的一种计算方法

文章介绍一种将含多环有向多重连通图分解为顶点带环且彼此孤立的有向简单图G1和顶点无环的有向多重连通图G2的方法，并在G2上用启发式搜索算法求非线性流水线的最小平均等待时间MAL。     

Voronoi图和遗传算法在对象识别中的应用

从对象识别的角度探讨了Ｖｏｒｏｎｏｉ图和遗传算法的应用，针对不同应用情形重新定义了基于Ｖｏｒｏｎｏｉ图与形的相似性度量，采用遗传算法以加快识别速度，并将视角和模型参数纳入染色体编码，实现了快速的类模型匹配的对象检测和识别。