基于子图同构的三维CAD模型局部匹配

针对整体相似性检索算法无法实施精确的局部结构匹配的问题,提出一种基于子图同构的三维CAD模型局部结构匹配算法.该算法通过提取CAD模型的B-Rep信息,将其表示为以面作为节点的属性邻接图.在局部匹配过程中,用户输入的局部结构被表示成"子图".待匹配的整体CAD模型被表示成"大图";则在整体CAD模型中.检索局部结构的问题就被转换成在"大图"中寻找同构"子图"的问题.子图同构是NP完全问题,通过利用CAD模型的面特征将图顶点有效细分,并利用已匹配顶点之间的邻接关系动态裁剪搜索空间,实现了快速的同构匹配.实验结果表明,该算法能实现精确的局部结构匹配,并且检索效率能满足实际应用要求.     

求解图同构的判定算法

图同构的判定性问题是图论理论中的一个难题,至今没有得到彻底解决。受Ulam猜想的启发,提出了一个新的判定图同构的充分必要条件：在子图同构的前提下,根据新增顶点及相应关联边的关系,利用子图同构函数,判断父图同构的充分必要条件。基于具有同构关系的对应点无限衍生技术,采用反证法证明了这个充分必要条件的成立。设计并实现了图同构的一个判定算法,通过实例验证了算法的正确性和有效性。     

图同构的一个充分必要条件

图同构的判定性问题是图论理论中的一个难问题,至今没有得到彻底解决。Ulam曾经提出过一个判定图同构的猜想,也称为图的重构猜想。提出了一个新的判定图同构的充分必要条件,即在子图同构的前提下,根据新增顶点及相应关联边的关系,判断母图同构的充分必要条件。基于具有同构关系的对应点无限衍生技术,采用数学归纳法证明了这个充分必要条件的成立。     

关于图同构复杂性的分析

图同构问题是指对两个图寻找顶点之间的一个一一映射,使得两图的边在该映射下也保持对应关系,该问题得到许多研究者的关注。在一些论文中对图同构问题的复杂性给出了错误的描述,有的给出了多项式时间算法。本文对此进行了讨论,并给出了一些反例来证明其算法的错误。根据图同构国内外目前的研究进展,图同构既未被归入P问题,也未被归入NPC问题,是一个尚未解决的问题,有待进一步研究。     

改进的基于分解的子图同构算法

分析了Messmer提出的基于分解的子图同构算法，指出了该算法存在的问题。从分解和组合两个方面对该算法进行了改进。改进的算法不仅解决了原有的问题，而且其性能有所提高。实验结果证明了算法的有效性。     

图同构中的一类顶点细分方法

提出一种顶点细分方法.基于顶点之间具有一定长度的路径数等信息,定义了一类顶点不变函数.将该方法与已有的一些顶点细分方法进行了比较.分析表明,基于路径数的顶点不变函数的细分效果,至少不差于基于顶点的度、距离等方法;而一些实例则表明前者要优于后者.基于路径数的顶点分类方法可以有效地用于图同构算法,能够降低所需比较的顶点数,达到快速搜索的效果.     

基于子图同构的子电路提取算法

从门级到功能模块级的子电路提取问题在大规模集成电路计算机辅助设计领域有广泛地应用,提出了基于子图同构的方法来解决该问题。针对子电路的特征,选择辐射路匹配和赋标号算法之一作为搜索的主算法。尽管子图同构问题是NP完全问题,算法对实际的电路是快速的,满足工程需要。     

无向图同构判定的并行算法

提出了一种判别无向图同构的方法，该方法根据无向图的邻接矩阵的特征值来判别出图的同构关系，而不需要其它附加信息。同时给出用Jacobi方法求出无向图的邻接矩阵的特征值的一种并行算法，它可以在分布式存储的多处理的多处理机上实现。实验结果表明，此方法是快速有效的，能在较短的运算时间内给出判断结果。     

不确定图间α-β子图同构匹配算法

子图查询返回图数据集合中所有包含查询图的数据图.在查询图和数据图同时为不确定性图的前提下,提出了不确定图间的期望子图同构定义和α-β子图同构匹配定义.不确定图间的期望子图同构是确定图上子图同构在概率图模型上的直接推广,不确定图间α-β子图同构利用两个限制阈值来衡量查询图和数据图间的匹配质量.文章详细阐述了α-β子图同构匹配的语义特点,分析了其和期望子图同构的联系和差别,设计实现α-β子图同构匹配判定算法.     

基于对称破坏的子图同构约束求解算法

为避免子图同构问题求解中重复解的产生,提高子图同构问题的约束求解效率,提出一种基于对称破坏的子图同构约束求解算法。基于解的对称破坏思想,改进自同构检测过程,通过置换群操作生成对称破坏字典序约束,构建子图同构问题的一种约束满足问题(CSP)模型,结合CSP的回溯算法对其求解。实验结果表明,该算法有效减少了对重复解的搜索,与传统算法相比明显提高了搜索效率。     

一种基于图同构和单向置换的报文摘要构造算法

为了保护信息的机密性和完整性,该文给出了一种新的报文摘要构造算法,这种新算法是基于图同构的。为了把报文与图联系起来,采用了基于单向置换的报文摘要生成算法,并证明了对该算法而言,不存在多项式时间的概率算法来找到一个“冲突”。最后给出了类似于MD5算法的构造实例。     

Isomorphism identification for epicyclic gear mechanism based on mapping property and ant algorithm

To achieve computer-aided design for mechanism, one method that can be applied is graph theory. During the process of kinematic structure enumeration using graph theory, isomorphism identification of graphs is an important and complicated problem. The problem is known to be NP-complete problem. It is very important to improve the isomorphism identification efficiency and reliability. The objective of this research work is to use ant algorithm to improve the isomorphism identification efficiency and reliability for epicyclic gear mechanism. Based on mapping property between graphs, the isomorphism identification problem can be changed into a matrix operation problem. Two graphs must be isomorphism if the two matrixes of the two graphs can be exactly by exchanging their certain rows and columns, whereas show the two graphs must be non-isomorphic. A mixed model was developed for isomorphism identification by integrating the ant algorithm and mapping property between graphs. The gratifying results can be achieved while parameters are selected in appropriate situation by using the model. Finally, a computer program has been developed in Visual C++. Some examples confirm the validity of the model. The work will be a reliable isomorphism identification algorithm for intelligent CAD of epicyclic gear mechanism.     

图同构的矩阵初等变换判定及算法设计

判断图同构的一种有用的方法是对图的邻接矩阵进行初等变换,变成另一个图的邻接矩阵。不幸的是,当初等变换后两个矩阵不能相等时,并不能说明两个图不同构,因为可能存在另一种变换途径,使得两个矩阵相等。另一方面,这种穷尽变换途径的方法有n!种可能(n为图的顶点个数);当n太大时,尝试每一种可能来说明两个图是否同构是不可行的,是一个NP难问题。文章提出了一个简单有效的判断图同构的方法。首先,利用邻接矩阵生成行码距异或矩阵和行码距同或矩阵;其次,寻找邻接矩阵、行码距异或矩阵、行码距同或矩阵间保持行元素一样的行-行置换;如果这种置换存在,则图同构,否则不同构。最后,根据行-行置换确定出同构函数,它给出了两个图的顶点间具有保持相邻关系的一一对应。     

Isomorphism for Graphs of Bounded Distance Width

In this paper we study the GRAPH ISOMORPHISM problem on graphs of bounded treewidth, bounded degree, or bounded bandwidth. GRAPH ISOMORPHISM can be solved in polynomial time for graphs of bounded treewidth, pathwidth, or bandwidth, but the exponent depends on the treewidth, pathwidth, or bandwidth. Thus, we look for special cases where ``fixed parameter tractable' polynomial time algorithms can be established. We introduce some new and natural graph parameters: the (rooted) path distance width, which is a restriction of bandwidth, and the (rooted) tree distance width, which is a restriction of treewidth. We give algorithms that solve GRAPH ISOMORPHISM in O(n ² ) time for graphs with bounded rooted path distance width, and in O(n ³ ) time for graphs with bounded rooted tree distance width. Additionally, we show that computing the path distance width of a graph is NP-hard, but both path and tree distance width can be computed in O(n ^k+1 ) time, when they are bounded by a constant k; the rooted path or tree distance width can be computed in O(ne) time. Finally, we study the relationships between the newly introduced parameters and other existing graph parameters. Received February 18, 1997; revised February 23, 1998.     

冲裁模CAD系统中的图形输入及排样分析

本文介绍了洛阳工学院研制的冲裁模CAD系统的技术特性，重点介绍了结点法输入图形时解决未知结点的数学方法及排样中的优化过程分析。     

基于面向对象的花边CAD系统的设计与具体实现

阐述了一个采用面向对象技术来设计刺绣ＣＡＤ系统的方法。通过对系统的分析,给出了系统的基本设计模型,确定了面向对象技术的基本元素－－对象,并对对象进行了详细设计。文章最后对系统进行了简单评价。     

基于回转面归并的CAD模型局部检索算法

针对不同CAD系统对包含回转面的同一零件的B-rep模型表示存在拓扑和几何上的差异,导致基于图匹配的三维CAD模型局部检索不能有效检索局部结构这一问题,提出一种基于回转面归并的局部检索算法。首先从用户输入的局部结构和待匹配的CAD模型中识别出由两个半面组成的回转面,利用欧拉操作将两个半面归并成一个整面。然后分别建立局部结构和待匹配的CAD模型的属性邻接图,则局部检索问题被转换成子图同构问题。最后利用CAD模型的面特征将图顶点有效地细分,并根据已匹配顶点之间的邻接关系动态裁剪搜索空间,实现了快速的同构匹配。实验结果表明,该算法能消除不同CAD系统生成模型的拓扑异构,实现局部结构的准确匹配,并且检索的效率满足实际要求。     

基于尺寸驱动的子午线轮胎CAD系统的开发研究

介绍了完全基于Windows系统平台并具有尺寸驱动功能的轮胎结构设计CAD系统（WTireCAD系统）的模块结构、设计界面、设计模块组成等,说明了该系统利用ObjectARX在AutoCAD环境下实现轮胎结构设计尺寸驱动功能的基本原理,展示了该设计系统的特点和新的设计环境。     

Metro Maps on Octilinear Grid Graphs

Schematic transit maps (often called “metro maps” in the literature) are important to produce comprehensible visualizations of complex public transit networks. In this work, we investigate the problem of automatically drawing such maps on an octilinear grid with an arbitrary (but optimal) number of edge bends. Our approach can naturally deal with obstacles that should be respected in the final drawing (points of interest, rivers, coastlines) and can prefer grid edges near the real-world course of a line. This allows our drawings to be combined with existing maps, for example as overlays in map services. We formulate an integer linear program which can be used to solve the problem exactly. We also provide a fast approximation algorithm which greedily calculates shortest paths between node candidates on the underlying octilinear grid graph. Previous work used local search techniques to update node positions until a local optimum was found, but without guaranteeing octilinearity. We can thus calculate nearly optimal metro maps in a fraction of a second even for complex networks, enabling the interactive use of our method in map editors.