基于改进Wang-代数生成连通图全部树的方法研究

提出了一种求连通图全部树的方法,通过对Wang-代数的改进,在生成连通图的全部树时,无需进行环和运算,从而减少算法的时间复杂度;同时能求得图的全部树,并且能保证同一个树不会重复产生,克服了传统Wang-代数法求连通图的全部树时产生的冗余项问题.算例表明方法的正确性和可行性,可有效地应用于复杂电网络的拓扑分析.     

公开钥密码体制RSA的一种随机攻击方法

给出了RSA加密算法中模n的几个有趣的性质.并把RSA的破译归结为求Diophantine方程x~2-y~2=n的非平凡整数解问题或n的连续奇数序列和表示问题,进而讨论了x~2-y~2=n的求解,并提出了一种时间复杂度为O(n~(1/6)的攻击RSA的随机算法。     

求赋权连通图最优树的用边率

对赋权连通图求最优树已有三种方法，用边率可以衡量方法的计算量．本文分别导出三种方法的用边率，理论分析与实例计算所得结论是选边法为最简算法．     

一种求简单多边形凸包的算法

提出了一种求简单多边形凸包的新算法。该算法的时间复杂性O（nlogn)次乘法和O（n)次比较。     

步数可变循环图中生成树的计数

生成树的个数是评估图(网络)可靠性的一个重要且被广泛研究的量.一般的图还无简单有效的算法计算生成树的个数,利用切比雪夫多项式的性质推出了步数可变循环图中生成树计数的在线性时间内即可实现的算法,并应用于具体的图中.     

巡检线路的哈密顿圈分割模型及算法

为求解带有时间周期约束和任务均分的多旅行商问题(MTSP),根据图论基本原理,借助最短距离树,结合贪婪算法和几何启发式算法,采用哈密顿圈分割覆盖的方法,建立了任务均分的巡检路线安排优化模型,设计了求解近似最优解的算法步骤,计算出近似最优的巡检人数和巡检路线安排,并计算了每位巡检人员的实际工作时间、巡检冗余时间和平均工作时间。进一步分析了不休息、休息、用餐等不同情形下的人员安排、巡检路线和工作量等情况。     

网络中最优控制树问题的贪婪算法

最优控制树问题是大型通讯、交通和供销网络中的一类突出问题.以最小支撑树问题的贪婪算法为基础,分析了最优控制树的本质特征,得到了求网络中最优控制树的一种启发式算法,并给出了算例.     

五对角线逆M-矩阵的Hadamard积

令M-1记所有n×n逆M-矩阵的集合,Sk记所有实矩阵其每个kk主子矩阵都是逆M-矩阵的集合.首先证得如果A,BM-1分别是上、下Hessenberg矩阵,则对任意H1,H2S2,AoB和(AoH1)o(BoH2)都是三对角线矩阵(因而是完全非负矩阵);其次证得如果A=(Aij),B=(bij)M-1满足对任意i-j3,aji=bij=0,则对任意H1,H2S3,AoB和(AoH1)o(BoH2)都是五对角线逆M-矩阵.     

似星树依Merrifield-Simmons指数的排序

设I(C)是图C的Merrifield-Simmons指数.对图G1和G2,若i(G1)〈i(G2),则记G1〈G2.只有一个顶点的度≥2的树称为似星树.对具有不同分枝的似星树的Merrifield-Simmons指数进行了比较,对具有相同分枝的似星树的Merrifield-Simmons指数进行了排序;并利用"<"关系,刻画出了似星树关于Merrifield-Simmons指数的极图.     

优先图化简算法研究

优先图可方便地描述程序的并发性,优先图与并发程序可以相互转换.发现了一种判断优先图冗余有向边的方法,同时找到了化简优先图的算法.使用该算法化简优先图以后,能使相应程序的并发控制复杂度降低.以化简饱和优先图为实例,相应程序并发控制的复杂度,由化简前的O(n2)降低为化简后的O(n).     

可分拟满Steiner树的结构性质与最优生成算法的研究

研究可分拟满Steiner树的结构性质与最优可分拟满Steiner树的生成算法.     

一类树Hosoya指标的研究

设G是一个分子结构图模型,即为一个具有n个顶点的连通图.则图G的Hosoya指标Z(G),是指图G中匹配的个数,包括空集. 该文讨论了四叶树Hosoya指标的第二大、第三大、第四大值.     

圆弧和直线段组成的封闭曲线快速求交

提出了一种由圆弧和直线段组成的封闭曲线快速求交方法：首先选择一个最优方向。根据最优秀向把封闭曲线分割为一系列单调链，然后通过拓展BentIey—Ottman扫描线算法对单调链进行求交，算法时间复杂度为O((n k)logm)，其中k为交点的个数，m为划分的单调链的个数。     

给定水平约束图的一类集成电路布线算法

针对水平约束图为星图的具有曼哈顿模型的通道布线,提出了一个依据图论模型的最优轨道高度布线算法.该算法根据通道上结点的水平约束图和垂直约束图特点,依次安排好每一个结点的布线轨道,进而通过通孔可以把所有的结点在2层轨道上布线完成.通过计算分析,该算法能够达到最优的布线高度.     

求直线程序通用输入的算法

直线程序对计算树模型是两个研究环（或域）上代数问题复杂性的较好的计算模型，特别是对问题复杂性下界的研究是很方便的。对任何一个直线程序Г，存在一个通用输入（Ｕ；ｕ），使得对Г的任何其它可执行的输入（Ａ：ａ），（Ａ；ａ）是（Ｕ；ｕ）的一个同态象。给出一个求直线程序通用输入的算法和一个计算实例。     

多分类-关联规则分类的一种改进算法

提出了一种基于多分类-关联规则的快速分类算法——FCMAR,该算法在建立频繁模式树(FP-tree)时裁减掉不能生成频繁规则的项目,因而可减少FP-tree的节点数目,有效地降低时间和空间复杂度,实验结果表明该算法是有效可行的.     

标号完全多部图的非平凡有根支撑森林的计数

文[1]中,柳柏濂与黄凤英研究了标号完全二部图的非平凡有根支撑森林的计数问题.在本文中,我们对该问题进行了自然地推广,解决了标号完全多部图的非平凡有根支撑森林的计数问题.进一步地.我们获得了标号完全多部图的包含s个s(≥0)平凡树的有根支撑森林的计数公式.     

关于图魔幻标号的运算关系

定义图的全魔幻空间及向量空间。证明了f,g∈P(G),则两标号f与g之间相差一个常数,对任何一个向量α_i∈V_(f_i),如果f_i∈P(G),则α_i可由其余α_(i-1)线性表示。给出了快速大规模地构造魔幻树的方法,得到了奇优美标号、优美标号、魔幻全标号之间相互转换的几个结果。     

多扇图中保Wiener指数的树

Wiener指数W(G)是指一个连通图G中所有顶点之间的距离之和.给定一个连通图G,若存在图G中一个子树T,使得W(G)=W(T),则称T为G的一个保Wiener指数的树.给出了对于满足特定条件的多扇图中具有保Wiener指数的子树,并证明了在多扇图中存在无穷多个这样的子树.     

流量约束最小生成树问题的分枝定界算法

研究流量约束最小生成树问题(CMST),它是通讯和网络优化设计中最为基础和重要的问题之一.给出一种分枝定界算法,详细阐述了算法的原理、搜索过程,数值结果表明,该算法是有效的,并且有较好的计算性能.