强竞赛图的强连通性

D=(V,A)为一个有向图,其中,V为顶点集,A为弧集,A中的元素是有序对(u,v),称为弧。设u和v是有向图D的两个顶点,若从u到v存在一条有向路,则称顶点v是从u可达的,或称从u可达v。若有向图D中任何两个顶点是互相可达的,则称D为强连通图。若有向图T中任意两个顶点之间恰有一条弧,则称T为竞赛图。一个强连通的竞赛图T称为强竞赛图。论文研究顶点个数大于的强竞赛图T的性质,并利用该性质给出了Moon定理的另外一种证明。     

2000年第24期擂台赛题目——有向图的连通性质判断

一个有向图的连通性包括弱连通性、单向连通性以及强连通性。     

Petri网仿真和自动化分析中的存储结构及算法研究

存储结构及算法是Petri网仿真和自动化分析研究中的重要内容，Petri网是一种特殊的有向图，通过对图的存储问题进行研究，提出了一种有向图的存储结构-树链式结构，给出了其构造算法，与其它有向图存储结构相比，它既可提高算法速度又能降低算法复杂性，树链式结构在Petri网仿真和自动化分析中应用优势明显，着重讨论了Petri网的树逻式存储结构，提出了基于该存储结构的可达树生成算法，所生成的可达树的树链结构形式，利于展开Petri网的各种分析算法。     

故障树自动生成技术的研究与实现

故障树自动生成技术在故障树生成中,根据控制系统流程图和有向图确定系统的邻接矩阵,利用邻接矩阵描述系统各子要素之间的直接关系,并求得的系统可达矩阵.通过搜索顶部结构各节点并结合故障树结构模型,从数据库中调用相关的因果模型,自动生成系统故障树.应用该技术大大增强了故障树的可读性,简化了系统故障树生成的复杂性,为故障树生成节省大量重复劳动,使生成的故障树具有更强的理论依据和可行性.     

求强连通分量的几种算法的实现与分析

有向图的强连通性是图论中的经典问题,有着很多重要的应用。该文给出了求强连通分量的Kosaraju、Tarjan和Gabow三个算法的具体实现,并对算法的效率进行了分析。     

有向图的强连通分量及应用

有向图的强连通分量应用非常广泛，比如有向图的强连通分量数量巨大的时候，为了更加高效必须要用缩点法。深度优先遍历是求有向图的强连通分量的一个有效方法，根据实现方式的不同，总体上，求有向图的强连通分量有三种算法，分别是Kosaraju算法，Gabow算法和Tarjan算法。三种算法的时间复杂度均为O（n＋e）（n为顶点数，e为边数）。     

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

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

递阶层次结构决策指标体系构建算法及应用

对决策问题及其支配关系采用加权有向图表示．首先设计一个指标用于衡量决策因素间的支配程度，并给出了决策问题可转换为递阶层次结构的两个前提条件；然后建立了3个多项武时间复杂度算法：第1个算法在最大程度保留决策因素支配关系的基础上，去掉决策因素间的循环支配；第2个算法利用可达矩阵的知识，将决策问题转化为递阶层次结构；第3个算法给出了各决策指标的权重．应用上述算法开发出智能评估专家系统，并以区域技术刨新能力指标体系的构建为例，介绍了该软件系统．     

有向图语言

经典形式语言有两条主线,就是自动机线索与形式文法线索。利用有向图理论和有向图半群理论建立了另一条线索——有向图语言,讨论了两类特殊的有向图语言——de Bruijn有向图语言和Kautz有向图语言,引入了连通语言及语言的直径等概念,计算出了de Bruijn有向图语言和Kautz有向图语言的直径。     

带权强分离信任委托路径搜索*

在委托证书路径搜索和一致性证明时,在Keynote提出的证书图的基础上,采用有向图中深度优先遍历的思想以及图的动态特性,提出了一种新的一致性验证算法,通过找出一条最佳的带权分离委托路径可以表达否定安全凭证,同时通过有向图的搜索边标记提高搜索效率并有效避免回路循环搜索的问题.     

一种强连通判定算法

提出一种新的强连通判定算法,使得在判定过程中的两次搜索可同时进行,便于并行运算.     

Halpern-type iterations for strongly relatively nonexpansive mappings in Banach spaces

In this paper, we note that the main convergence theorem in Zhang et al. (2011) [21] is incorrect and we prove a correction. We also modify Halpern’s iteration for finding a fixed point of a strongly relatively nonexpansive mapping in a Banach space. Consequently, two strong convergence theorems for a relatively nonexpansive mapping and for a mapping of firmly nonexpansive type are deduced. Using the concept of duality theorems, we obtain analogue results for strongly generalized nonexpansive mappings and for mappings of firmly generalized nonexpansive type. In addition, we study two strong convergence theorems concerning two types of resolvents of a maximal monotone operator in a Banach space.     

Algorithms and complexity analysis for some flow problems

Several network-flow problems with additional constraints are considered. They are all special cases of the linear-programming problem and are shown to be -complete. It is shown that the existence of a strongly polynomial-time algorithm for any of these problems implies the existence of such an algorithm for the general linear-programming problem. On the positive side, strongly polynomial algorithms for some parametric flow problems are given, when the number of parameters is fixed. These algorithms are applicable to constrained flow problems when the number of additional constraints is fixed.Work on the paper was done while at Stanford University and IBM Almaden Research Center. This research was partially supported by NSF PYI Grant CCR-8858097.     

Almost sure limit theorems for the maxima of some strongly dependent Gaussian sequences

We proved some almost sure limit theorems for standard strongly dependent Gaussian sequences in nonstationary cases under some mild conditions.     

A simplified correctness proof for a well-known algorithm computing strongly connected components

The computation of the strongly connected components of a directed graph is one of the fundamental algorithmic graph problems. Linear-time algorithms with simple implementations are known. Here a simplified correctness proof for one of these algorithms is presented.     

基于维度频率相异度和强连通融合的混合数据聚类算法*

k-Prototypes算法对初始点选取的敏感性导致聚类结果具有随机性,并且忽视样本数据点与聚类集合中已有样本的总体差异.针对此问题,文中提出基于维度频率相异度和强连通融合的混合数据聚类算法,首先通过多次预聚类产生大量子簇,然后根据子簇之间的连通关系,采用强连通融合的策略得到最终的聚类结果.在UCI数据库中3个混合属性数据集上的实验表明,相比k-Prototypes算法及已有的混合属性聚类算法,文中算法具有更好的聚类质量,从而验证文中算法的优越性.     

强安全两方认证密钥协商方案*

基于CK（Canetti-Krawczyk,CK）安全模型的认证密钥协商（authenticated key agreement ,AKA）方案不能抗临时私钥泄露产生的攻击,因此,CK模型下被证明是安全的AKA方案也许仍然是不安全的。2007年,LaMacchia等人首次提出了eCK（Extended Canetti-Krawczyk,eCK）安全模型,该模型被认为是当前AKA方案最安全的模型。但LaMacchia等人提出的方案不能抗哈希值泄露产生的攻击。为了解决上述问题,一个新的强安全认证密钥协商方案被提议。新方案满足抗密钥泄露伪装、己知会话临时信息安全和能抗哈希值泄露攻击等特性,只要每方至少有一个未泄露的秘密,那么新方案在eCK模型下就是安全的,而且新方案是已知同类方案中运算量最少的。     

Stable discrete solution of coupled singular mixed partial differential problems

This paper deals with the construction of stable discrete numerical solutions of strongly coupled singular diffusion mixed partial differential problems. After discretization, using a matrix difference scheme, the resulting coupled mixed partial difference problem is treated using a discrete separation of variables method which avoids solving algebraic systems. Existence, stability of solutions, its construction, algorithm and example are given.     

Cyclic routing algorithms in graphs: Performance analysis and applications to robot scheduling

In this paper we revisit and extend the algorithm for the cyclic project scheduling problem which was originally proposed by Romanovskii (1967). While the algorithm has been derived for fixed numerical data, we show how it can be extended to handle the problems with interval data. We also propose a new algorithm for the cyclic scheduling problem with interval data that extends the parametric method developed by Megiddo (1979) and runs in strongly polynomial time.     

The density matrix renormalization group algorithm on kilo-processor architectures: Implementation and trade-offs

In the numerical analysis of strongly correlated quantum lattice models one of the leading algorithms developed to balance the size of the effective Hilbert space and the accuracy of the simulation is the density matrix renormalization group (DMRG) algorithm, in which the run-time is dominated by the iterative diagonalization of the Hamilton operator. As the most time-dominant step of the diagonalization can be expressed as a list of dense matrix operations, the DMRG is an appealing candidate to fully utilize the computing power residing in novel kilo-processor architectures.