广义Kautz有向图GK(3,n)的反馈数的界

对于给定的图G的顶点集的子集F,如果删除F使得剩余子图是无圈子图,则称子集F为图G的反馈点集。研究了广义Kautz有向图GK(d,n)的反馈点集。令f(d,n)表示广义Kautz有向图GK(d,n)的所有反馈集合中顶点个数最少的集合的个数(即广义Kautz有向图GK(d,n)的反馈数),给出了GK(3,n)的反馈数的上界,即 f(3,n)≤n+5n8 － 3n4－ 4n7+3。     

Petri网语言与传统形式语言的关系

本文介绍了一种形式语言－Ｐｅｔｒｉ网语言，并讨论了Ｐｅｔｒｉ网语言与传统形式语言（正规语言，上下文无关语言，上下文有关语言以及递归枚举语言）的关系。     

ω幂上下文无关语言及其封闭性质

本定义了ω幂上下无关语言ω－ｐ－ｃｆｌ和一类ω下推自动机ω－ｐｄａ，给出了它们的关系，借助于ω时序转换器ω－ＳＴ，讨论了ω－ｐ－ｃｆｌ类的某些封闭性质，证明了对于ω－ｐ－ｃｆｌ类ζ，ξ（δ）＝｛Ｓ（Ａ）｜Ａ∈ζ，Ｓ是一个ω－ＳＴ｝＝｛ｈ２（ｈ＾－１１（Ａ）∩Ｒ）｜Ａ∈ξ，Ｒ是一个ω正规语言，ｈ１是一个同态，以及ｈ２是一个λ无关同态｝。     

关于Z规格说明语言中模式的剖析

1.引言形式规格说明语言一般是提供一套称为语法域的记号系统和一个称为语义域的对象集合,以及一组精确地定义哪些对象满足哪个规格说明的规则。规格说明是语法域中的句子。它用数学表示法精确地描述了软件系统必须具备的性质。 Z是目前比较流行的一种形式规格说明语言,它以一阶谓词逻     

如何判断有向图的连通性？

(一)问题 2000年第24期擂台赛的问题是有向图的连通性判断。 对一个有向图,忽略所有有向边的方向性而得到对应的一个无向图,如果该无向图是连通的,即其中任意两点有通路相连,则称原有向图是弱连通的:如果在原有向图中任意两点间至少有一点至另一点的通路,则称该图是单向连通的:而如果原图任两点之间一定既有甲至乙,也有乙至甲的通路,即有双向通路,则称该图是强连通的。 例如,图1是一个非弱连通非单向连通与非强连通图:图     

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

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

基于ECA规则约束有向图的工作流建模

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

Unicontour Isomorphic Factorizations of de Bruijn and Kautz Digraphs

In the topology of information networks, problems arise of existence and implementation of a decomposition of some network into factor-graphs that have no common edges and to which certain specified features are assigned. Special attention is given to isomorphic expansions and factorizations of graphs in the case where obtained components are simplest topologic network structures. The factorized character of Bruijn and Kautz graphs on a set of specific families of unicontour oriented factors is proved.     

On the k-tuple domination of de Bruijn and Kautz digraphs

In a digraph G, a vertex u is said to dominate itself and vertices v such that (u,v) is an arc of G. For a positive integer k, a k-tuple dominating set D of a digraph is a subset of vertices such that every vertex is dominated by at least k vertices in D. The k-tuple domination number of a given digraph is the minimum cardinality of a k-tuple dominating set of the digraph. In this letter, we give the exact values of the k-tuple domination number of de Bruijn and Kautz digraphs.     

Minimum feedback vertex sets in shuffle-based interconnection networks

Given a graph G, the problem is to construct a smallest subset S of vertices whose deletion results in an acyclic subgraph. The set S is called a minimum feedback vertex set for G.Tight upper and lower bounds on the cardinality of minimum feedback vertex sets have been previously obtained for some hypercube-like networks, such as meshes, tori, butterflies, cube-connected cycles and hypercubes. In this paper we construct minimum feedback vertex sets and determine their cardinalities in certain shuffle-based interconnection networks, such as shuffle-exchange, de Bruijn and Kautz networks.     

一种表示有向图的表方法及其应用

图的表示方法很多,各有其优缺点.采用不同的表示方法,可获得图的不同的时空性能.本文阐述了图的一种新表示方法,该方法用一种命名规则将有向图表示为节点标签表,给出了由节点标签表产生节点链的算法.并用这种称为表方法研究了有向图的回路性质,特别地将它应用于研究de Bruijn回路、欧拉回路和哈密顿回路,给出了计算欧拉回路和哈密顿回路的新方法.本研究表明该方法具有较好的理论和实用价值.     

Lukasiewicz逻辑值上下文无关语言的代数刻画

提出了基于Lukasiewicz逻辑的下推自动机（l-VPDA）的概念,从代数角度研究了此类自动机的性质,同时建立此类自动机的代数刻画,即利用模糊状态构造,证明了任意以终状态方式接受模糊语言的l-VPDA与状态转移为经典函数且具有l值模糊终状态的l-VPDA间的相互等价性;并证明任意以空栈方式接受模糊语言的l-VPDA与状态转移除一步转移为模糊的以外,其余都是经典函数的l-VPDA是相互等价的;详细研究了l-值模糊上下文无关语言的代数和层次刻画,以及对于正则运算的封闭性。     

n-Dimensional Processor Arrays with Optical dBuses

dBus-array(k,n) is an n-dimensional processor array of kⁿ nodes connected via k^n–1 dBuses. A dBus is a unidirectional bus which receives signals from a set of k nodes (input set), and transmits signals to a different set of k nodes (output set). Two optical implementations of the dBus-array(k,n) are discussed. One implementation uses the wavelength division multiplexing as in the wavelength division multiple access channel hypercube WMCH [7]. WMCH(k,n) and dBus-array(k,n) have the same diameter and about the same average internode distance, while the dBus-array requires only one tunable transmitter/receiver per node, compared to n tunable transmitters/receivers per node for the WMCH. The other implementation uses one fixed-wavelength transmitter/receiver per node and the dilated slipped banyan switching network (DSB) [17] to combine time division and wavelength division multiplexing.     

求有向图的所有Hamilton回路的新方法

引入了单源单汇线性有向k-部图，设计了该结构上的删除算法、合并算法和输出算法，在此基础上给出了判断有向图是否含有H回路的多项式时间算法和计算H回路数的多项式时间算法，给出了求解有向图的所有H回路算法，并通过实例验证了算法的有效性，解决了H回路的判定、计数和求解问题。     

一般有向图法的实现及其应用

讨论了一般有向图法实现中的元部件完全模型知识表示、算法实现中的子算法以及对一个专家系统环境TEE的改造等问题,并给出了一个应用实例.     

用分层关联方法求有向图中所有Hamilton回路的算法

首先建立了有向图中初级通路的关联关系,并对初级通路的关联关系进行了分析,得到了关于初级通路关联关系的一些重要结果.然后,对初级通路的关联关系进行了分级分层.在此基础上,设计了求有向图中所有Hamilton回路的算法.该算法利用长度为k的初级通路及其分层关联关系逐步求长度为k+1的初级通路及其分层关联关系的方法,求得有向图的所有Hamilton回路.通过理论分析可以看到,所设计的算法与已有的求有向图的所有Hamilton回路的算法相比,避免了大量的重复计算,从而降低了算法复杂度,为求解Hamilton回路问题提供了新思路.     

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

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