简单有向图情形下Adfm猜想的证明

就简单有向图情形下证明了Ａｄáｍ关于“若Ｄ是包含有向圈的有向图,则存在某弧,把它反向后将减少Ｄ中有向圈的数目”的猜想是正确的     

有向图为Hamilton图的一个充分条件

在文献[2]中,Bang-Jensen等人猜想,如果对n阶强连通有向图D中每一对不相邻的,且具有公共内邻或公共外邻的顶点对x,y,都有它们的度和不小于2n-1,则D是Hamilton图.本文证明若对上述x,y,如果它们的度和不小于2n-1与5/2n-9/2中的最大者,则D是Hamilton图.     

工程陶瓷材料的磨削加工性评价方法研究

提出了一种工程陶瓷材料磨削加工性综合评价的新方法.应用图论中的有向图理论,以材料磨削加工性属性为顶点,以各属性之间的相互关系为边,建立了陶瓷材料磨削加工性评价的有向图模型.根据有向图模型,建立磨削加工属性矩阵,并由矩阵的积和式函数计算出材料的磨削加工性指标,从而判断材料的磨削加工性.有向图模型可以综合考虑多种属性及属性间的相互关系,可对陶瓷材料的磨削加工性做出正确、完整的评价.论文选择陶瓷材料的硬度、断裂韧性和弹性模量3个力学性能参数作为磨削加工属性,根据所提出的评价方法,对4种典型工程陶瓷材料的磨削加工性进行评价,并根据磨削加工性指标进行排序,在材料机械加工之前确定其磨削加工性.通过磨削实验验证评价结果.评价结果将对陶瓷材料加工中工具和工艺参数的确定具有指导作用.     

全不可分矩阵的k重上广义指数集

目的研究全不可分矩阵的ｋ重上广义本原指数．方法采用图论与数论相结合的方法．结果与结论给出了ｎ阶全不可分矩阵类的ｋ重上广义本原指数集,并对其极矩阵集合作了部分刻划．     

有向图并行计算中一种新的结点调度算法

在基于有向图的并行计算中,给定图剖分后,如何设计结点调度方案使得并行执行时间最短,是典型的NP完全问题.针对此问题,文中提出一种新的基于顺逆交替迭代技术的启发式调度算法,并给出该算法的并行实现.严格的理论推导证明,新算法在一定的假设条件下,从任何初始调度方案出发,均可以单调收敛.在数百个处理器上的并行数值实验表明,与常用的调度算法相比,新算法可在付出很少的开销代价下显著提高整体并行效率.     

一类异构多智能体系统有向图下的广义平均一致性分析

本文对有向图下离散时间一阶二阶混合的异构多智能体系统广义平均一致性问题进行研究.首先给出了该异构系统广义平均一致性的基本概念.在此基础上,针对平均一致性研究中对交互拓扑为平衡网络的局限,提出了一种基于辅助变量的线性一致性协议,对每一个智能体增加一个辅助变量,用于记录个体的状态更新.采用图论、非负矩阵理论、特征值扰动等方法进行分析证明,表明该协议使得异构多智能体系统在任意强连通有向图下达到广义平均一致性.并对收敛值的性质进行了分析.最后,通过仿真对该结论进行了验证.     

基于DS-VSMM的声网络低空机动目标跟踪

针对低空机动目标的声网络无源跟踪问题,提出一种基于有向图切换的变结构多模型算法.首先,将多个声传感器组网并对其时延的方位角数据进行配准,改善无源声探测网络的融合性能.其次,通过变结构多模型对目标状态进行估计,并利用有向图切换方法对新激活的模型分配权重,跟踪结果为多个模型估计结果的融合输出.通过与交互式多模型算法的仿真比...     

Minimal separators in dependency structures: Properties and identification

This paper considers some properties of (locally) minimal separators in oriented graphical dependency models, i.e., in Bayesian networks, Gaussian networks, and hybrid networks. Statements and rules are inferred from the criterion of d-separation and acyclic property of digraph. Necessary conditions are established that should be satisfied by members of (locally) minimal separators. Patterns of evidences are found that allow one to identify the presence or absence of an edge without an extensive search for a separator. These means facilitate the efficient inference of a model structure with the help of constraint-based algorithms. Translated from Kibernetika i Sistemnyi Analiz, No. 6, pp. 17–32, November–December 2008.     

图论在输煤程控路径选择中的应用

针对丰鹤公司输煤控制系统中，输煤流程路径中的选择，以图论的深度优先搜索和广度优先搜索遍历有向图．介绍了输煤程控系统中路径选择程序的设计，实际应用表明按照图的深度遍历搜索和广度遍历搜索来设计流程路径是一种比较简捷直观有效的流程路径设计思想。     

Improved Algorithms for Dynamic Shortest Paths

We describe algorithms for finding shortest paths and distances in outerplanar and planar digraphs that exploit the particular topology of the input graph. An important feature of our algorithms is that they can work in a dynamic environment, where the cost of any edge can be changed or the edge can be deleted. In the case of outerplanar digraphs, our data structures can be updated after any such change in only logarithmic time. A distance query is also answered in logarithmic time. In the case of planar digraphs, we give an interesting tradeoff between preprocessing, query, and update times depending on the value of a certain topological parameter of the graph. Our results can be extended to n -vertex digraphs of genus O(n ^1-ε ) for any ε>0 . Received September 24, 1996; revised May 13, 1998, and January 20, 1999.