二分图的Laplace矩阵的最大特征值

图的Laplace矩阵的谱,在物理、化学和计算机等学科有着广泛应用。但是,求图的Laplace矩阵的谱,是很不容易的。文章通过分析二分图的结构,研究了二分图的Laplace矩阵的特点,利用非负矩阵的经典理论和图论方法,导出了一般二分图的Laplace矩阵的最大特征值的界值。     

一个生成组合的新算法

文章发现了一个生成集合{1,2,...,n}的所有组合的新算法,不仅其理论是初等的,且算法程序化特别容易.利用集合{1,2,...,n}的组合与n位二进制数之间的一一对应关系,该算法从n位二进制数00...0开始,仅仅使用当前n位二进制数一次一个地生成下一个n位二进制数,直到得到最后n位二进制数11...1时算法终止....     

一类特殊de Bruijn有向图的谱

分析了一类特殊de Bruijn有向图-B(2，n)的结构，获得了B(2，n)的谱．B(2，n)的特征值为0与2，且它们所对应的重数分别为2^n-1与1．     

一个生成Hasse图的有效算法

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

相容关系的最大相容类的生成算法

集合A上的二元关系R称做相容关系,如果它是自反的、对称的。若B是集合A的非空子集,且B中的任意两个元素都有相容关系R,则称集合B为相容关系R的相容类。不能真包含在任何相容类中的相容类即为最大相容类。文章研究了生成相容关系的最大相容类所需要的理论,设计了生成相容关系的最大相容类的实用算法——优化广度优先搜索。     

一类(0,1)矩阵的谱

矩阵的特征值是矩阵理论的一个重要概念,然而,求一个矩阵(哪怕是阶数很低的矩阵)的特征值的精确值,却是非常困难的。文章运用图论的理论和方法,巧妙地解决了一类(0,1)矩阵的谱,为(0,1)矩阵的谱理论研究,提供了一种新的思维方法。     

求非负矩阵最大特征值与特征向量的C-W方法

幂法是求矩阵最大特征值及最大特征向量的经典方法.依据C-W函数及其理论,文章给出了求非负矩阵最大特征值及最大特征向量的有效迭代方法--C-W方法.论证了其收敛性,给出了其误差估计,并与幂法进行了比较. C-W方法算法简单,不必附加任何收敛条件.计算结果表明,C-W法的收敛速度比幂法快.     

生成图的全部极大独立集的一般方法

图的极大独立集问题是图论中重要的NPC问题,独立集具有广泛的应用领域,如编码理论、信道分配、资源配置、纠错码理论等.文章运用拟序关系理论,系统研究了生成图的全部极大独立集的一般方法,该方法简单实用,程序化实现容易.