最大公共子图的约束符号求解方法

【目的】探索求解两个图最大公共子图的方法。【方法】建立最大公共导出子图的软约束满足问题(Soft CSP)模型,提出代数决策图(ADD)的符号求解算法。首先,分别对两个图中的变量和值域进行编码,完成两个图的ADD表示;其次,基于深度优先分支定界算法的思想,利用符号ADD的相关操作,实现对最大公共导出子图的求解。【结果】算例结果表明,该方法准确可行。【结论】该方法能有效缩减搜索空间,从而提高问题的求解效率。     

产品设计过程建模及重组

产品设计过程是一项复杂的系统工程,是多种知识的有效集成和耦合．文中在综合分析目前设计过程建模技术的基础上,提出了基于扩展有向图和模糊设计结构矩阵的信息建模方法,对活动间的信息依赖进行了定量表示,通过对设计活动进行分解、撕裂和级别划分．实现了设计过程的优化重组．进而对耦合活动间的信息相关程度进行模糊排序,指导耦合活动的分解,并给出了算法流程．最后以冲裁模具设计过程为例,验证了上述方法的有效性和实用性．     

平面图与对偶原理

该文利用对偶原理创造性地解决了平面图、连通图及对偶图之间的相互关系问题,纠正了长期以来对于平面图及其同构的错误认识,指出平面图必为连通图,平面图本质上是画在同一平面上的顶点、边、面均不相交的连通图。两个平面图的同构指这两个平面图的顶点、边、面之间均有一一对应关系。面是平面图区别于非平面图的本质特征。同构的平面图的对偶图必同构,事实上,平面图的对偶图是唯一的。任意一个平面图都伴有一个隐图,而该隐图实质上是该平面图的对偶图,该隐图可(根据对偶原理)通过D—过程画出。平面图与其对偶图互为对偶。显平面图与其隐对偶图合称为相伴对偶图。     

图论与群的凯莱图

从图论的观点研究群的凯莱图,利用有向图同构理论讨论了群凯莱图的同构,并将图论中子图概念加以拓广．给出了群的凯莱图子图的概念及应用．     

基于自适应图调节和低秩矩阵分解的鲁棒聚类

聚类是数据挖掘和机器学习领域的重要研究内容,一般会先基于数据样本构建相似图,再基于相似图将样本划分到相应的类中。但是真实的数据经常被损坏,导致学习的相似图不准确,从而直接影响聚类结果。为解决这些问题,提出一种面向鲁棒聚类的自适应图调节和低秩矩阵分解的方法,该方法的核心思想是:将原始数据X分解为纯净数据D和噪声数据S,再基于纯净数据构造拉普拉斯矩阵并进行自适应图调节。随后,给出一个联合学习框架,将数据分离、自适应图正则、噪声消除和低秩矩阵分解集成到一个目标函数中。利用增广拉格朗日乘子法分别更新变量。最后,在理论上证明算法的收敛性并进行实验。实验结果表明所提出的方法与现有一些方法相比有一定优越性。     

图的同构判定算法:关联度序列法及其应用

提出了图的同构判定新算法,即关联度序列法和黄金分割关联度序列法,后者的计算时间复杂性远远低于2N（N为图的顶点数）,已接近于多项式时间复杂性,该算法可应用于很多能用图来描述的式识别等实际问题。     

任意图同构判定及其应用

建立了任意图的伴随电路模型,使用电路分析方法求解伴随电路,通过解出的节点电压来确定原图拓扑结构的对应顶点,并由此提出了可应用于任意图的同构判定算法.     

基于多维数据列向量2D图表示的多维筛可视化组合分类器

提出一种新型的可视化组合分类器--多维筛分类器.该分类器集成了属性数据的2D图表示、图像处理与模式识别技术.其根本思想是将数据矩阵的属性数据映射为2D多元图,然后将多元图通过像素图及图像处理技术转换为子分类器,利用组合分类器规则将各子分类器构成多维筛可视化组合分类器.通过引入交互式方法,选择最优多元图用于分类.通过对Iris数据集的分类试验表示,散点图多维筛与极坐标多维筛的分类精度可以达到98.67%和97.33%.     

图同构判定的新方法

图的同构问题由来已久,并且它的应用十分广泛。例如:确定一个图的自同构群的构造的问题和它有紧密联系;在有机化学上我们可以利用图的同构判定方法来确定同分异构物。因此,寻求图同构的判定方法是一项引人入胜的工作。提出了一个新的判定方法(定理1)可以方便的确定两个图是否同构。此外,还得到了某一类图的同构判定的一个较强的条件(定理2)。     

遗留软件系统的一种重构方法

遗留系统（Legacy系统）通常依赖不同概念结构。由于语义层的冲突，难以实现互操作，通过重建语义层对Legacy系统进行概念化封装，并通过语义转换规则，解决遗留系统之间的语义互操作问题，该方法是实现信息系统灵活重用与集成的有效途径。     

单群的点传递图的GI-性质

针对点传递图的同构问题,类似于Babai关于Cayley图为CI图的充分必要条件,给出了点传递图为GI-图的判别准则,并研究了单群的点传递图的GI-性质.     

SideKnot:Edge Bundling for Uncovering Relation Patterns in Graphs

The node-link diagram is an intuitive way to depict a graph and present relationships between entities.Addressing the visual clutter induced by edge crossing and node-edge overlapping is a challenging task as the size of graph outgrows the visualization space.Many edge bundling methods are proposed to disclose high-level edge patterns.Though previous methods can successfully reveal the skeleton graph structure,the relation patterns at the individual node level can be overlooked.In addition,most edge bundling algorithms are computationally complex,which prevents them from scaling up for extremely large graphs.In this article,we extend SideKnot,an efficient edge bundling method to cluster and knot edges at the node side.Our proposed method is light,runs faster than most existing algorithms,and can reveal the relation patterns at the individual node level.Our results show that SideKnot can disclose a node’s standing in the graph as well as the directional connection patterns to its peers.     

基于无向图转有向图的同构判别

无向同构图指的是在两个图中寻找顶点之间的映射关系,通过映射使原本形式各异的两图中的各条边保持对应的关系.为了有效提高寻找无向同构图的时间效率、简化操作,首先研究了无向图同构的矩阵存储方式,并针对性地提出了把无向图转换为有向图的同构算法.与矩阵存储算法相比,该判定算法的时间更为简短.最后给出了实现该算法的相关程序以及用该算法对无向图进行判定的过程和结果.     

一种判定树同构的BULT算法

将判定两棵树的同构问题转化成"图的同构"问题和"两棵树根结点之间的对应关系"问题的判定.基于图与树的关系,提出一种自底向上分层遍历图结点(Bottom-Up Layer Traversing)的方法,简称 BULT方法,解决以上两个问题,从而得到一种线性的时间复杂度与空间复杂度的树同构判定算法,并给出了算法正确性证明.该算法很容易扩展为图同构的判定算法.     

一种从企业遗留智能系统学习OWL本体方法研究

为规避基于文本的本体学习中尚未解决的中文分词歧义问题,实现企业遗留智能系统中拥有的大量领域知识的复用,提出一种从遗留智能系统学习OWL本体的方法.在分析关系数据库模式、元组集与OWL本体之间元素对应关系的基础上,详述了该方法的具体步骤.与现有相关方法相比,本方法针对的数据源蕴含更丰富的领域知识,更加适合实际的工程应用;通过一个简单、低时间复杂度的转换算法,而非中间模型或大量抽象规则,从关系数据库模式中自动获取相应的OWL本体部分;并按照一定的先后顺序将遗留系统中范例、规则知识项(元组集)移植为OWL本体中对应的个体.一个面向企业工装工时定额的遗留智能系统应用实例证实了该方法的有效性.     

（P,P）图的可嵌性定理

设G是一个简单无向图,称G是(P,P)图,如果|E(G)|=|v(G)|.若G同构于6某个子图,则称G可嵌入6,本文用极其简捷的方法证明了:阶数大于9的(P,P)图可嵌入其补图内的充要条件是G不和图(1)中的任一个图同构。     

基于标准编码的有向标记频繁子图挖掘算法

针对大部分频繁子图挖掘算法,基于无向图而不适用于更具有实际意义的有向图的挖掘的现状,通过对无向图挖掘算法gSpan中编码结构的扩展,采用改进的规范形式,使编码适用于有向图领域。并使用针对有向图的DADI++存储结构来存储图集,简化了数据访问操作的代价。另外在挖掘中使用Hash表存储同构图的Hash地址和支持度,避免对图集的重复扫描和直接的同构测试。在实际数据集上运行的实验结果表明提出的Dspan算法是正确的,并比FFSM算法效率更高。     

Structural indexing for 3D solid digital library

In a very large digital library that support computer-aided collaborative design, an indexing process is crucial whenever the retrieval process has to select among many possible designs. In this paper, we address the problem of retrieving important design and engineering information by structural indexing. A design is represented by a model dependency graph, therefor, the indexing problem is to determine whether a graph is present or absent in a database of model dependency graphs. we present a novel graph indexing method using polynomial characterization of a model dependency graph and on hashing. Such an approach is able to create an high efficient 3D solid digital library for retrieving and extracting solid geometric model and engineering information.     

有阻塞OXC节点的图表示

提出了有阻塞OXC节点的图表示方法。该方法的基本思想是用图来替代交换能力受限制的节点,而此图由交换能力不受限制的节点和容量受限的边组成。文中以典型的阻塞OXC节点为例,给出了它们的图表示,并通过例子得出一般的OXC节点图表示求法的一些普遍结论。     

模糊图的乘积运算及相关分解

定义了两个模糊图的字典乘积并给出了一个模糊图能分解成两个模糊图的强乘积、直接乘积、字典乘积的充分条件或必要条件。 证明了两个模糊图的偏模糊子图的强乘积、直接乘积、字典乘积是这两个模糊图的强乘积、直接乘积、字典乘积的偏模糊子图。 最后给出了与这三种乘积运算相关的同构定理。