关于出现网的S切

出现网是研究Petri网的进程的工具,而出现网的S切又是研究进程的重要概念。讨论S切的基本性质：定义并证明S切M在E的元素e的作用下发生的变换M→u[e]=（u-·e）Ue·以及发生变换的条件。定义并证明S切u在E的元素e的反作用下发生的变换v→v[e-1]=（v-e·）U·e以及发生变换的条件;证明对于任意S切u有u[e][e-1]=u,对于任意S切v有v[e-1][e]=v。证明每一个S切u（≠w1）都能够被某一个e作用,每一个S切v（≠W0）都能够被某一个e反作用。     

强竞赛图的强连通性

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

Fourier基本图象和Fourier变换图形对

一个二维图形f(x,y)的二维Fourier变换F(u,v)也是一个二维图形。互为Fourier变换的图形可由图1的Fourier基本图形来得到。图1的Fourier图形由离散Fourier矩阵[A_N]构成。若图象的x、y坐标系和二维谱的u、v坐标系的原点在矩阵中心,x和u的正轴在右方,y和v的正轴     

旋转圆锥网格及其在玻璃/钢结构中的应用

圆锥网格是计算机辅助建筑设计中一类新的平面四边形网格,具有良好的等距性质,非常适用于玻璃/钢结构,而旋转曲面是建筑设计中的常用形状.通过引入旋转圆锥网格的概念,并利用圆锥网格的定义,给出了构造旋转圆锥网格的简单方法.证明了只在旋转曲面r(u,v)=(f(u)cosv,f(u)sinv,g(u))的v参数方向进行均匀分割,而在U参数方向进行任意分割,则所产生的平面四边形网格为圆锥网格;并研究了旋转曲面为圆锥曲面和圆柱曲面的特殊情况;最后给出了基于旋转圆锥网格的玻璃结构造型实例.该方法简单易行,对计算机辅助建筑设计中的玻璃/钢结构造型有一定的实际应用价值.     

关于Bubblesort-star网络的距离控制数

对于任意的正整数l,连通图G的顶点子集D被称为距离l-控制集,是指对于任意顶点v(∈)D,D中至少含有一个顶点u,使得u和v在G中的距离不超过l.图G的距离l-控制数是指G中所有距离l-控制集的最小基数,1-控制数常常称为控制数.给出了Bubblesort-star网络的控制数、距离2-控制数和距离3-控制数的界,而且针对某些低维Bubblesort-star网络的这几类控制数给出了更好的界.     

关于图的分数k-因子存在性的一些结果

设g(x)≤f(x)是定义在V(G)上的两个整数值函数,h(e)∈[0,1]是定义在图G的边集E(G)上的函数。令dGh(x)=移e∈Exh(e),其中Ex={xy:xy∈E(G)}。若对所有的x∈V(G)都有g(x)≤dGh(x)≤f(x)成立,称h是G的一个(g,f)-表示函数。Gh是图G的一个支撑子图使得E(Gh)={e:e∈E(G),h(e)≠0},则称Gh是G的一个分数(g,f)-因子。文章给出,若对V(G)中的任意两个顶点u和v,G-{u,v}有分数k-因子存在。则G有一个分数k-因子不含图G中任意给定的边e∈E(G);当G有分数1-因子F=Gh存在时,对任意e∈F,G-V(e)有分数k-因子存在,则G有分数k-因子。     

图Pu,v(n)的邻强边染色

u,v两点间连接n条内部不相交的路,其中最多有一条长度为1,记做Pu,v(n)。给出一个算法,利用计算机寻找边染色的规律,进一步给出了Pu,v(n)的邻强边染色法,从而确定了Pu,v(n)的邻强边染色数。进一步讨论了至多含有两个顶点度大于2的部分简单连通图的邻强边色数。     

一种感应式静电传感探头的灵敏度理论值

感应式探头主要用在各种静电计及静电场测量仪表上,其基本结构如图1所示.当探头靠近电势为V_0的被测带电体时,因静电感应,感应电极A将输出微小电位v(A与接地外壳绝缘),比值v\v_0≡s称为探头灵敏度.如果     

环Fp uFp vFp uvFp上的二次剩余码

针对环Fp+ uFp+ vFp+ uvFp上的二次剩余码进行了研究,其中u2=u,v2=v,uv=vu,p是一个奇素数.首先引入了环Fp+ uFp+vFp+ uvFp上长为n的循环码的相关知识,用幂等元的形式定义了环Fp+ uFp+vFp+uvFp上的二次剩余码,给出了其定义和性质,并讨论了它们与其扩展码之间的关系和对偶性质.最后,给出了环F3+uF3+vF3+uvF3上长为11的二次剩余码的幂等生成元的具体形式.     

数据集中强邻近对的查询方法

数据集中的强邻近对查询在地理信息系统、图像处理和多媒体数据库等领域有着重要的应用.为了解决数据集中强邻近对查询问题,基于Voronoi图对数据集中强邻近对问题进行了详细研究,给出了在无障碍物和有障碍物环境下查询数据点集中强邻近时的定理和算法,设计了相应的数据存储结构,对在无障碍物和有障碍物环境下的查询数据集中的强邻近对问题进行了实验分析.该方法可较好的解决曲面空间和有障碍物空间中的数据集中强邻近对的查询问题.     

梯图的点可区别全染色（n≡4（mod8））

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素及其本身所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法：三角排序。利用该排序的结果证明了当n≡4（mod8）和C4n-1/2＋2〈m≤C4n/2＋2时,梯图Lm■Pm×P2的点可区别全色数为n。     

梯图的点可区别全染色（n=7（mod8））

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素所构成的色集合不同,其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法——三角排序,利用该排序的结果证明了当n=7（mod8）且Cn-1^4/2＋2〈m≤Cn ^4/2＋2时,梯图Lm≌Pm×P2的点可区别全色数为n。     

梯图的点可区别全染色（n≡5（mod8））

一个图的全染色被称为点可区别的即对任意两个不同点的相关联元素及其本身所构成的色集合不同。其中所用的最少颜色数称为G的点可区别全色数。本文定义了一种排序方法：三角排序。利用该排序的结果证明了当n≡5（mod8）和C4n-1/2＋2〈m≤C4n/2＋2时,梯图Lm≌Pm×P2的点可区别全色数为n。     

A tight lower bound on the size of visibility graphs

The visibility graph of a finite set of line segments in the plane connects two endpoints u and v if and only if the straight line connection between u and v does not cross any line segment of the set. This article proves that 5n - 4 is a lower bound on the number of edges in the visibility graph of n nonintersecting line segments in the plane. This bound is tight.     

Depth-first search is inherently sequential

This paper concerns the computational complexity of depth-first search. Suppose we are given a rooted graph G with fixed adjacency lists and vertices u, v. We wish to test if u is first visited before v in depth-first search order of G. We show that this problem, for undirected and directed graphs, is complete in deterministic polynomial time with respect to deterministic log-space reductions. This gives strong evidence that depth-first search ordering can be done neither in deterministic space (log n)^c nor in parallel time (log n)^c, for any constant c > 0.     

Channel assignment with separation for interference avoidance in wireless networks

Given an integer /spl sigma/>1, a vector (/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/), of nonnegative integers, and an undirected graph G=(V, E), an L(/spl delta//sub 1/, /spl delta//sub 2/,..., /spl delta//sub /spl sigma/-1/)-coloring of G is a function f from the vertex set V to a set of nonnegative integers, such that |f(u)-f(v)|/spl ges//spl delta//sub i/, if d(u,v)=i, for 1相似文献   

A database system of mechanical components based on geometric and topological similarity. Part II: indexing, retrieval, matching, and similarity assessment

This paper presents an approach for retrieving and matching similar designs in a database of mechanical components. The retrieval and matching process is based on the geometric and topological similarity between mechanical components. The process constitutes five steps: (i) transforming the component from the CAD system in STEP format, (ii) building an attributed graph for it, (iii) abstracting the graph into some geometric entities, (iv) retrieving a set of similar graphs based on the abstracted data, and (v) matching the graph of the new design with each graph on the set of similar graphs. This paper addresses the last three steps. Retrieving and matching mechanical parts based on their shape has many applications such as cost estimation and process planning. Matching similar parts and calculating a similarity index for them has applications in manufacturing evaluation, design by case-based reasoning, robotics, and computer integrated manufacturing. Having a database system of mechanical components based on part shape serves in all of these applications.     

图上下文及在图距离计算中的应用

图结构的特征提取及相似性度量是计算机视觉和模式识别中的重要研究内容。针对传统的方法对存在非刚性变换的图结构难以充分描述这一问题,给出一种基于图的上下文(GC)描述子的图结构信息描述及距离度量方法。首先,通过对图的边缘进行等距离散取样得到该图的采样点集;其次,基于图的采样点集给出图的上下文描述子;最后,采用推广的推土机距离(EMD)方法实现图的上下文描述子的距离度量。不同于图的编辑距离计算方法,所提方法不需要定义代价函数。实验表明该方法对于一些非刚性变换前后的图的距离计算具有较好的效果。     

Decision tree complexity of graph properties with dimension at most 5

A graph property is a set of graphs such that if the set contains some graph G then it also contains each isomorphic copy of G(with the same vertex set).A graph propoerty P on n vertices is said to be elusive,if every decision tree algorithm recognizing P must examine all n(n-1)/2 paris of vertices in the worst case.Karp conjectured that every nontrivial monotone graph property is elusive,In this paper,this conjecture is proved for some cases,Especially,it is shown that if the abstract simplicial complex of a nontrivial monotone graph property P has dimension not exceeding 5, then P is elusive.     

The k-neighbourhood-covering problem on interval graphs

Let G=(V, E) be a simple connected graph and k be a fixed positive integer. A vertex w is said to be a k-neighbourhood-cover (kNC) of an edge (u, v) if d(u, w)≤k and d(v, w)≤k. A set C ? V is called a kNC set if every edge in E is kNC by some vertices of C. The decision problem associated with this problem is NP-complete for general graphs and it remains NP-complete for chordal graphs. In this article, we design an O(n) time algorithm to solve minimum kNC problem on interval graphs by using a data structure called interval tree.