二次分配问题的骨架分析与算法设计

骨架分析是近年来NP-难解问题研究的热点，对于衡量问题的相变、难度及算法设计具有重要意义．骨架的理论分析及在算法设计方面的应用还处于起步阶段，从QAP问题入手，对QAP骨架进行了理论分析，证明寻找QAP问题的骨架属于NP．难解问题，不存在多项式时间的算法可以保证得到QAP问题的骨架，为局部最优解交叉来获得近似骨架提供了合理性解释，在此基础上，利用偏移实例构造方法，提出了基于偏移实例的近似骨架算法．其基本思想是：首先为QAP实例构造偏移实例，其最优解恰是原QAP实例的一个全局最优解；然后利用现有算法求得新实例的多个局部最优解，通过对局部最优解求交得到近似骨架；将近似骨架固定以得到规模更小的搜索空间，最后在新空间上求解，拓广了骨架理论研究的范围，所提出的算法为NP-难解问题的通用算法设计提供了一种新思路。     

有偏单位元的环

在[2]、[3]文中建立了与[1]文中相平行的ρ—理想理论,本文将证明有偏单位元的ρ—交换环、ρ—理想、ρ—素理想、广义ρ—素理想、ρ—准素理想、ρ—互质、ρ—相关等概念与通常的概念完全一致,因此,关于满足ρ—理想极大条件、有偏单位元、ρ—交换环的ρ—理想分解定理实际上是Noether环的分解定理。本文还将给出一个理想与ρ—理想一致的充分条件。     

图中有边不交的3个1─因子的一个新充分条件

Ｗｉｎ于１９８２年证明了２ｎ阶Ｏｒｅ－（１）型图有边不交的３个１－因子．本文改进这个结果，得到一个新的充分条件：２ｎ（ｎ≥１０）阶２－连通Ｏｒｅ－（－２）型图Ｇ有边不交的１个Ｈａｍｉｌｔｏｎ图和１个１－因子，除非Ｇ是附图中所示的图之一．     

图中有边不义的3个1—因子的一个新充分条件

ｉｎ于１９８２年证明了２ｎ阶Ｏｒｅ－（１）型图有边不交的３个１－因子。本文改进这个结果，得到一个新的充分条件：２ｎ（ｎ≥１０）阶２－连通Ｏｒｅ－（－２）型图Ｇ有边不变的１个Ｈａｍｉｌｔｏｎ图和１个１－因子，除非Ｇ是附图中所示的图之一。     

一种噪声启发式聚类算法

启发式聚类算法的搜索空间中布满了局部极小值"陷阱",从而使得算法容易过早收敛而无法获得高质量聚类结果.文章给出了一种噪声启发式聚类算法NHCA (Noising Heuristic Clustering Algorithm),该算法在搜索空间中增加一组由强至弱的噪声来扩大启发式搜索的局部范围,以保持搜索空间的多样性,达到避免局部极小值影响和提高聚类质量的目的.大量实验结果表明,噪声法对提高启发式聚类算法质量是十分有效的.     

3—连通正则无爪图的Hamilton圈

证明了每一个3－连通k-正则无爪图G，当G的点数n≤5k-5时，G包含一个Hamilton圈。     

具有加权特性的门限认证加密机制

可转换的认证加密机制允许指定的接收者同时对消息进行恢复和验证.而多重认证加密机制允许签名群组的多个签名成员合作生成信息的多重认证签名密文.该文结合基于中国剩余定理的加权门限秘密共享方案,构造一种加权门限机制,进而提出了一种具有加权特性的门限认证加密机制.在该机制中,每个群成员根据重要性的不同,可以被分配一个正的整数作为权重.只有当生成签名密文的群成员的权重超过预定阈值时才能生成合法的认证密文.     

域K上三维结合代数的分类

我们知道任何理论都要对研究对象进行分类,而域K上有单位元的一维、二维结合代数的结构已经清楚了。本文对域K上含有单位元的三维结合代数的结构进行探索。在对代数进行直和(半直和)分解时,如果直和(半直和)因子中的理想含有单位元,那么就认为这时的代数结构已经清楚了。否则,要求直和(半直和)因子中的理想均为弱单代数(即不含