图的伪对集

本文定义了图的伪对集是可以含有环的对集,给出了一个图有完美伪对集的充分必要条件并证明了有关最大伪对集的两个定理,从而推广了Tutte及Berge的对集定理。     

求邻接对集的一个有效算法

图的一个邻接对集是指由其互不相交的相邻边对构成的边的子集,且去掉这些相邻边对后,所得之图是连通的．本文提供了求最大邻接对集的一个有效算法,并指出此算法可以求图的最大亏格     

基于改进的粘贴模型求解图最大独立集的DNA算法

改进的DNA粘贴模型在解决SAT问题时所需的寡核苷酸片段数量有显著降低,对改进的粘贴模型做了进一步的改进,建立了图最大独立集的一种改进的DNA粘贴模型.首先将图的独立集问题转化为可满足性问题,然后利用本文改进的粘贴模型给出了图的最大独立集的DNA算法.最后通过一个实例给出算法实现并求出了最大独立集.     

一个求外平面图最小反馈点集的多项式时间算法

如果从一个图中去掉某些顶点后得到的导出子图是无圈图，则所去的那些顶点组成的集合就是原图的反馈点集。本文讨论外平面图的反馈点集并给出了一个求外平面图最小反馈点集的多项式时间算法。     

图顶点着色问题的质粒DNA计算

图的着色问题是著名的NP问题,有着重要的实际意义。比如通讯系统的频道分配、考试排考场问题等方面有直接应用。图的着色问题采用DNA计算方法很多,有表面DNA计算,粘贴DNA计算。本文提出质粒DNA计算,首先把顶点着色问题转化为求最大独立集问题,然后给出了图顶点着色问题的质粒DNA分子生物实验,利用限制性内切酶的特性切割有边相连的顶点,得到最大独立集,在试验中特别引入了一个备用试管,最后给出一个具体的实例。实例给出具体的着色方案,证明了该质粒DNA算法有效并且是可行的。     

求解单圈多部图的匹配算法

给出了一个多部图及其匹配问题的定义,提出了求解单圈多部图匹配问题的一个算法。该算法提出多部图顶点间的可达性定义,并使用试探与缩小规模相结合的方法以及求二部图的最大匹配算法,求解单圈多部图的最大匹配问题。经过验证,算法的效率比较高。     

图的最大独立集数上界

本文记明了简单连通图的最大独立集数上界定理和与图的最大独立集有关的其它几个定理。这些定理为构造求图的最大独立集的启发式算法奠定了基础。     

一个生成Hasse图的有效算法

Hasse图是偏序集关系图的一种简明而有效的表示。文章证明了偏序集的唯一盖住关系Cov(A)等价于两个关系的复合运算,从而可转化为两个矩阵的布尔乘积,给出了一个求盖住关系Cov(A)的有效算法,从而方便、快捷地生成偏序集的Hasse图,完善了有关Hasse图的理论及算法。     

基于图的频繁项集挖掘

通过对Apriori算法的频繁项目集的分析研究,给出了基于图的频繁项集挖掘算法.该算法在求频繁K-项集的过程中只需一次扫描数据库,避免了Apriori算法需多次扫描数据库的不足.同时,由于在有向图中利用有限节点之间的路径求频繁K-项集,该算法减少了Apriori算法中需多次进行连接运算的不足.     

一个求图的最大圈的启发式算法

本文给出了无向图、有向图存在哈密顿圈或存在包含顶点数为N_1的最大圈的充分条件,在此基础上给出了求最大圈的找通路一扩大回路算法,这个算法是启发式的,但是有效的。利用此算法可以求出任意图的最大圈,也可以用来搜索图的最佳哈密顿圈。     

一种三边Switch-box的布线问题及其图论算法

本文将一种VLSI中的三边Swithc-box的布线转化为图论中的求偶图的最大非交叉匹配问题,并在文献[1]思想的基础上提出了一个求偶图的最大非交叉匹配的有效算法。该算法已在IBM PC/XT上用FORTRAN77实现。最后给了算法用于三边Switch-box布线的实例。     

关于简单图最大匹配的矩阵算法研究

定义了简单图匹配边的匹配优先指数、竞争集、匹配余集及匹配余图等重要概念,从最大匹配的定义及匹配边与非匹配边的竞争关系着手,在图的关联矩阵基础上,提出了求无权简单图最大匹配的一种操作简单、编程容易的新算法——"表单作业法".     

伪对集复盖图

若过图G的每条边都有一个亏数为d的伪对集,则称图G为亏数d-复盖图。本文给出了一个图是亏数d-复盖图的充分必要条件及该条件的一些应用,从而推广了Little 的结果.     

1-可扩偶图的刻划

设G是一个具有二分类(X，Y)的偶图且M是G的一个完美对集。文章证明：G是1—可扩图当且仅当G有如下耳朵分解G=e P1 P2 … Pr使得e∈M并且每个只是起始和终止边都在E(G)＼M中的M-交错路。文章还给出一个有效算法判定一个偶图是否1—可扩图并找出该图的耳朵分解。     

针对带约束匹配搜索的扩展Kuhn-Munkres算法

提出了扩展的Kuhn-Munkres算法,可解决带下界约束的局部匹配存在性问题,即在匹配全集的给定子集中,搜索得到一个二分图匹配满足其边权和大于给定阈值．扩展Kuhn-Munkres算法构造了一棵以Kuhn-Munkres算法中间过程为节点的搜索树,利用搜索优先级和剪枝,将算法时间复杂度降低至二分图匹配全集与给定子集差集规模的多项式函数．      

偶查询优化的图论方法

本文针对一类特殊的多关系查询——偶查询,提出了一种建立在图论偶图和匹配理论基础上的查询优化方法,这种方法具有多项式复杂性。     

A new algorithm for degree-constrained minimum spanning tree based on the reduction technique

The degree-constrained minimum spanning tree (DCMST) is an NP-hard problem in graph theory. It consists of finding a spanning tree whose vertices should not exceed some given maximum degrees and whose total edge length is minimal. In this paper, novel mathematical properties for DCMST are indicated which lead to a new reduction algorithm that can significantly reduce the size of the problem. Also an algorithm for DCMST to solve the smaller problem is presented which has been pre-processed by reduction algorithm.     

寻找最大独立集的算法

提出两种基于贪婪思想的局部搜索算法寻找给定图的最大独立集,通过测试第二种算法在图密度小时更优与第一种算法.由于局部搜索算法的缺陷,修改邻域函数与顶点的选择是进一步研究的问题;考虑到算法的有效性,时间复杂度和近似算法的比较也是值得进一步研究的方向.