图的平面性添加算法

本文给出了同时完成图的平面性判定,平面化,以及平面嵌入的一个算法。同时给出了这一算法的机器化结果。     

PQ-树断点距离中心问题的复杂性和精确算法

PQ-树是一种树状数据结构,用来表示元素排列集合.虽然消逝物种完整基因组序列具有不确定性,但是根据同源物种可以确定部分基因的相对位置,所以可以利用PQ-树来存储消逝物种的基因组.在生物学中,进化树用来表示物种之间的进化关系.当构建生物进化树时,叶子结点表示现存物种,其基因组用排列表示;内部结点为祖先物种,其基因组用PQ-树表示.为了确定物种间的进化关系,需要确定PQ-树可以产生的排列与已知排列之间的距离.以断点距离为标准,研究了p-PQ-树断点中心问题,即从给定PQ-树中产生一个排列,使之与给定的p个排列的断点距离之和最小.证明当p≥2时,p-PQ-树断点中心问题是NP-完全的.当p=1时,p-PQ-树断点中心问题是参数化可计算的,针对1-PQ-树断点中心问题,提出了时间复杂度为O(3\\+Kn)的参数化算法,其中K为最优解的断点距离.     

哈密尔顿图的判定算法

提出了哈密尔顿图判定的一个充要条件 ,并给出了具体的实现算法。用C语言设计了相应的程序验证了此算法。     

一个快速平面性算法

Rubin最近在System/360 Model67上实现了Demoucron等人的平面性算法,发现它在通常大多数情况下要比目前堪称最优的Hopcroft ＆Tarjan算法约快一倍。本文改进了Rubin的算法,使它不再需在整个P(Gk)中而仅需在其任一子等价类中探索可嵌链,且因采用了较恰当的数据结构,也使所需的总存储量从Rubin的约39m剧减到约22m(m是给定图的顶点个数)。     

用二进制判定图的功能测试

一、前言本文探讨一个把二进制判定图应用于功能测试的问题。先探讨一些普通的数字器件图并给出其具体使用的例子。接着简单讨论功能测试,特别是讨论如何把功能测试视为一种发生和执行一组精密筹划的实验过程。然后将可看到,这种图是提供自动发生一组实验的简便的方法。由此将推导出好几组这样的实验,包括运算器的实验。最后将在执行实验的许多方法中,讨论几种方法,以及一些有关的问题和技术。     

关于用吴—刘定理判别图的平面性的复杂性问题

吴文俊和刘彦佩教授在七十年代用代数拓扑的方法,给出了一个新的判别图的平面性的方法,即吴-刘定理。本文对给定Hamilton路的图进一步简化了吴-刘定理,据此可以给出一个判别此类图的平面性的在实际运算中更为有效的线性算法。     

新的二部图判定算法

二部图是现代图论中一类非常重要的图,然而关于其判定的充要条件却很少,而且用算法实现它们很复杂.需要指数级的时间代价.利用图的广度优先遍历,提出了一个易于实现的二部图判定的充要条件:无向图G是二部图当且仅当G的广度优先生成森林中的同一层上的任意两点在G中不邻接.给出了该判定条件的实现算法,算法的时间复杂度是O(n2),很好地解决了二部图的判定问题.     

一个增量式判定树学习算法INDUCE

ＩＮＤＵＣＥ算法采用自顶向下判定树归纳的学习方法,不仅具有健壮性好,效率高和正确率高等优点,还具有增量学习能力,可以动态修正概念描述的不足,该算法还运用了构造性归纳的思想,在学习过程中生成新的描述子,使概念描述空间搜索的效率得到提高。运行实例表明,ＩＮＤＵＣＥ具有很好的应用前景。     

一种简单的图的平面性判断算法的实现研究

Malgrange、Malgrange和Pertuiset三人合作提出O（n2）时间复杂度的平面性判断算法，尽管效率不是那么理想，却易于理解，并且算法结束时能够给出平面图的一种平面嵌入，另外算法仅涉及到割点的检测、图的计算机表示、图的分割、图的遍历等较为基础的问题。从而能够很好地适应教学及入门对直观性，可实现性的需要。尽管这个方法已经较为直观。但是由于图的平面嵌入在计算机中的表示较为困难等问题．其算法具体如何实现依然需要细心研究。     

连通图中关节点的判定算法

文章提出了一种连通图关节点的矩阵求解算法,该算法数据结构形式简单,求解方便且易于理解,用C语言设计了相应的程序验证了此算法.     

二叉判定图最优化算法研究综述

对近年来二叉判定图(BDD)最优化算法的成果和发展趋势进行了综述和讨论，重点介绍精确排序算法和动态启发式排序算法．给出了BDD优化算法的改进建议：用不完全枚举法的优势和随机过程动态规划策略改进BDD优化算法．     

判定树算法在计算机取证中的应用

随着网络犯罪的日益猖獗,计算机取证正逐步成为人们研究与关注的焦点.为了能从海量的可疑数据中发现证据,数据挖掘技术的参与必不可少.首先介绍了在计算机取证中比较常用的数据挖掘分类分析方法,然后介绍其在计算机取证原型系统中的实现和应用,最后给出了进一步研究的方向:多样证据的提取及其之间的关联.     

图的树分解算法及其应用

一个图G=(V,E)的树分解是将结点集V的子集作为树T的节点,使得在T上任意一条路径上的两个端节点的交集包含于该路径上的任意一个节点中。将T上最小(节点)对应子集的元素个数减1定义为分解树T的宽度,用宽度最小的分解树T的树宽度定义图G的树宽度。一个合取范式(Conjunctive Normal Form,CNF)公式F可以用一个二分图G=(V∪C,E)表示(公式的因子图),其中变元结点集V对应公式F中的变元集,子句结点集C对应公式F中的子句集,变元在子句中的正(负)出现用实(虚)边表示。忽略公式因子图中边上的符号,得到一个二分图。文中研究了图的树分解算法,并将树分解算法应用到CNF公式的因子图树分解。通过实验观察公式因子图的树宽度与求解难度之间的联系。     

用转换成多级图的方法判定图的H性质

给出了哈密顿图判定问题的一个算法。思想是先将简单无向图转换成多级图,然后证明简单无向图中哈密顿回路存在性与多级图中简单路径(定义见正文)存在性的等价性,最后通过多级图中简单路径存在性的判定实现简单无向图H性质判定。     

关于用户兴趣度的判定树算法的优化

判定树学习有很多算法,着重研究对引入用户兴趣度参数的ID3算法在面对多值属性时的快速分类的优化,提高计算速度,节约计算时间。     

基于种群协同进化的分类判定树构造算法

提出一种基于两种群协同进化的分类判定树构造算法，该方法充分利用协同进化的强搜索能力和渐进学习等特点，通过设计两个协同进化的种群：一个表示选择的属性子集，另一个表示如何构造判定树，保证在搜索曩优判定树的过程中同时对属性子集选择、判定树的构造进行综合优化，最终获得一个较好的分类判定树。作为实验验证，我们把新算法应用到一个困难的真实问题一胸癌诊断，结果表明了新算法的有效性。和其它算法的实验结果比较，新的分类方法比C4.5和文[1]方法构造出更好的判定树，即去除了多余的属性、具有更高的分类精度。     

数据挖掘中判定树算法SLIQ的设计与应用

分析了一种用Gini指标进行属性选择的SLIQ算法,讨论了提高效率的可行方法.把算法用到电力市场发电竞价决策系统中,通过对发电商的竞标能力进行挖掘,获取的知识对发电商的决策有重要现实意义.     

图的树分解及其算法应用研究进展

图的树宽和树分解是图子式理论中发展起来的两个重要概念。图的树分解由于其本身的特性使得它在算法设计中有着极其重要的意义。从图的树宽特性、图的树分解算法、图的树分解在复杂算法问题求解中的应用等方面对近年来的相关研究进展做了深入的分析和介绍,结合一些简洁的实例分析了一些重要的原理和方法,讨论了其中的一些问题,并给出了今后的一些研究方向。