赋权有向图最小生成树的表上作业法

每一赋权有向图可用一个赋权表来表示。本文在借助于赋权表而不是赋权有向图本身讨论圈和生成树的基础上,给出了一种求解赋权有向图最小生成树的新方法——表上作业法,证明了方法的最优性。该方法简单易行,借助于计算机Ｓｐｒｅａｄｓｈｅｅｔ软件,如ＭｉｃｒｏｓｏｆｔＥｘｃｅｌ,可很方便地进行大规模复杂问题的求解。     

An Explicit Integer Programming Model of the Minimal Spanning Tree Problem for Digraphs with Asymmetric Weights

1.INTRODUCTIONTheminimalspanningtreeproblemfortheundirectedgraphhasbeenwellstidiedanduntilnowmanyefficientalgorithms[4]havebeenproposed.Ithasbeenobservedbymanypeoplethatastrikingnumberofquitediversemathematicalproblemscanbeformulatedastheproblemsinintegerprogramming.Althoughtheminimalspanningtreeproblemhasbeenformulatedinthisway,suchas[3,5-8],buttheyareallimplicit,thatis,theformulationcontaillssomeunformulatedstatementsintheconstraintsuchasX:spanningtreewhichmakestilefornnllationunsolvabl…     

平面格图生成树的计数

设ｔ（ｍ,ｎ）和ｔ（ｍ,ｎ）分别是平面ｍ×ｎ格图生成树和对称生成树的数目,从而给出了ｔ（３,ｎ）和ｔ（３,ｎ）的闭公式以及ｔ（ｍ,ｎ）递推式阶的估计．     

应用动态生成树的GPU显存数据复用优化

针对手工优化GPU(Graphic Processing Unit)显存级数据复用过程复杂和编译时优化数据复用开销过大的问题,提出了一种基于动态生成树在运行时进行数据复用的优化方法,可为程序员提供一种透明且高效简单的优化方式.该方法将已经执行的GPU计算任务的数据访问抽象为生成树的叶子节点,利用动态生成树管理GPU数据访问信息,实现了运行时GPU显存级数据的复用优化,并通过运行时对生成树的搜索和维护,动态地发掘和优化GPU显存级数据复用,因此,在编程时不需要进行复杂且困难的数据复用分析,直接调用文中提出的运行时库就能有效减少程序执行过程中CPU内存和GPU显存之间的冗余数据传输次数,从而提升应用的运行性能.实验结果表明,使用文中提出的优化方法可有效消除未进行数据复用优化的CPU-GPU应用程序中的冗余数据传输,最大加速比达原始执行的3～10倍,额外开销不到优化后程序总执行时间的5％.     

Euler生成子图边数的一个定理

证明了设G=(V,E)是2-边连通的简单图,| V |=n,δ(G)是G的最小度,若δ(G)≥max{4,n-4/5}时,G存在Euler生成子图H,使得| E(H)|/|E(G)|≥2/3;即此时Catlin的2/3--猜想成立.     

基于Prim算法最小生成树优化的研究

通过Prim算法的研究寻找局部最优解的迭代过程,用布尔向量U和V-U表示集合中的边,根据权值的关系找到快速有效的算法来构造最小生成树.从理论上分析了算法的性质和时间复杂度.通过实例分析, 证明了该算法有效性并在现实生活中得到的广泛应用.     

循环图中生成树个数的渐近性质

就给定的整数s1,s2,…,sk,1≤s1≤s2≤…≤sk,给出了一种简单的方法来计算Cn^21,s2,…,sk中生成树个数的渐近性质,证明了该渐近性可以归结为求解一个次数为2sk-2的多项式,并将这种计算方法应用到若干个循环图作为例子．     

哈密尔顿图的一类新的局部化充分条件

设L为图G的一个导出子图 ,若有 x ,y∈V(L) ,只要dL(x ,y) =2就有max{dG(x) ,dG(y) }≥ |G| / 2 ,则称L有局部Fan性质 .该文证明了以下结果 .G是一个 2_连通的 {K1.3 ,B1} -free图 .对任意一个整数s≥ 0 ,若G的任一个导出子图L∈ {Bi,0≤i≤s;Zs+2 }均有局部Fan性质 ,则G是Hamiltonian图 ,除非s=2且G H9.由此得到每个 2_连通的 {K1.3 ,Bi,0≤i≤s;Zs+2 }_free图除s =2且该图同构于H9外 ,均为Hamiltonian图 .     

依托区域优势 发展特色经济的实践——从晋皖湘三省比较中对山西转型跨越发展的思考

介绍了在中部崛起中安徽和湖南两省取得的新进展,分析了两省凭借各自优势确立目标,以取得发展的特色经验,提出了以科学发展观为统领,谋求区域经济协调可持续发展的启示。     

图的L(p,1T) 点标号问题

本文将距离为2的点的限制条件放松到支撑树上，提出了一类新的点标号问题，并相应给出了这种标号数的一般上界。