有向图收缩法及其应用

本文基于分子图形分割技术,把对称矩阵对应的无向图收缩法推广为任意矩阵对应的有向图收缩法,并把它应用于非稳态动力学,简化了本征多项式的运算。     

关于广义Hadamard矩阵及其对应有向图类的特征

Hadamard矩阵在信号处理方面有重要应用,而Hadamard矩阵是广义Hadamard矩阵的特殊情形.讨论了广义Hadamard矩阵对应简单有向图类的特征及其相互关系;给出了广义Hadamard矩阵对应简单有向图的特征值的性质,从而证明了有向图的邻接矩阵是广义Hadamard矩阵的必要条件,为简单有向图是偶阶的;并得到了广义Hadamard矩阵在Kronecker积下的性质.为区组设计和编码理论提供了一些新的方法,并在信源编码中有重要的应用.     

一些 DNA 图的标号

为了读取DNA序列,Blazewicz等人提出了(α,k)-可标号的有向图的概念,称有向图D是DNA图若D是(4,k)-可标号的.基于此,证明了(α,k)-可标号的有向路和有向圈的充要条件.设T是一棵只有一个入(出)度为0的点的定向树,还证明了T是(α,k)-可标号的有向图的必要条件和T是DNA图的充要条件.     

扩张的局部内(外)半完全有向图的可迹性

扩张的局部内(外)半完全有向图是半完全有向图的一个重要的推广图类.本文利用有向图中点可多重插入到路中的方法,得到了扩张的局部内半完全有向图可迹的一个度限制下的充分条件.利用扩张的局部外半完全有向图是扩张的局部内半完全有向图的逆图的性质,对应地得到扩张的局部外半完全有向图可迹的一个充分条件.     

基于有向图的工作流过程建模与实现

探讨了有向图在工作流过程建模中的应用以及其模型的XML文挡形式化描述,并在此基础上进一步给出了工作流过程模型与XML文档元素之间映射以及转化的主要策略．     

有向图的强连通性分析及判别算法

文中用可达矩阵分析了有向图的强连通性,并给出了一种判别有向图为强连通图的新方法。     

有向图2k·_5及2k·_7的优美性

杜之亭（１９９４）中提出的猜想：在ｎＣ２ｐ＋１（ｐ∈Ｎ）,在ｎ≡０（ｍｏｄ２）时是优美图。证明了,当ｐ＝２,３时为真     

解决无线传感器网络能量洞问题的贪婪算法

无线传感器网络中的能量洞问题是影响网络寿命的关键因素之一。在基于环模型的多跳传感器网络中,通过优化所有环的传输距离可以有效地延长网络寿命。提出了一种近似的贪婪算法（ASGT）,该算法将最优传输距离序列问题转化为最优生成树问题,在降低搜索（算法）复杂度的同时得到与最优解近似的结果。模拟实验证明了采用ASGT算法的网络寿命逼近于理想最优序列下的网络生命时间,并且与已有的文献算法相比,ASGT可以延长网络寿命两倍以上。     

GC-MCR:有向图约束指导的并发缺陷检测方法

约束求解应用到程序分析的多个领域,在并发程序分析方面也得到了深入的应用.并发程序随着多核处理器的快速发展而得到广泛使用,然而并发缺陷对并发程序的安全性和可靠性造成了严重的影响,因此,针对并发缺陷的检测尤为重要.并发程序线程运行的不确定性导致的线程交织爆炸问题,给并发缺陷的检测带来了一定挑战.已有并发缺陷检测算法通过约减无效线程交织,以降低在并发程序状态空间内的探索开销.比如,最大因果模型算法把并发程序状态空间的探索问题转换成约束求解问题.然而,其在约束构建过程中会产生大量冗余和冲突的约束,大幅度增加了约束求解的时间以及约束求解器的调用次数,降低了并发程序状态空间的探索效率.针对上述问题,提出了一种有向图约束指导的并发缺陷检测方法 GC-MCR (directed graph constraint-guided maximal causalityreduction).该方法旨在通过使用有向图对约束进行过滤和约减,从而提高约束求解速度,并进一步提高并发程序状态空间的探索效率.实验结果表明:GC-MCR方法构建的有向图可以有效优化约束的表达式,从而提高约束求解器的求解速度并减少求解器的调用次...     

多物理数值模拟中一种有效的并行耦合方法

在实现多物理并行数值耦合模拟中,需要处理多个物理过程之间网格、并行区域分解的差异.针对该同题,该文基于三维流体力学与激光传播耦合的并行数值模拟,提出了一种实用的并行耦合方法:引入辅助状态将本地插值与通信相分离;构建并行耦合图并定义主导属性,以确定过程间传输的最小数据集合;提供并行数据重分配算法来完成通信.并行数值结果表明:该方法是有效的,在64台处理机上使整体程序获得50.07的加速比.