2—有向循环图的同构

本文得到了2-有向循环图 G(a,b,N)与 G(a＇,b＇,N)同构的充要条件为:(a,b,N)=(a＇,b＇,N)=K且 a＇b≡ab＇(mod KN);或 a＇a≡b＇b(mod KN),这里(x,y,z)表示整数 x,y,z 的最大公约数。     

增删边对最短路径影响的研究

在有向图中加入或删除一些边时，可能有多种可选的方案，通过对各种方案影响最短路径的大小进行研究；给出联通权重值的定义和对最短路径贡献大小的规定，并给出在多种可能方案中选择最佳方案的具体算法     

PACKING AND COVERING WITH ARBORESCENCES

The aim of this note is to exhibit some recent results on packing and covering witharborescences.     

赋权有向图中最小生成树问题的显式整数规划模型

就具有不对称权重的有向图中的最小生成树问题,本文首次建立了相应的显式整数规划模型,这一模型可以成功地运用整数规划软件包如Ｌｉｎｄｏ等求解。并进一步将这一模型推广到随机最小生成树问题,也即具有随机变量权重的有向图中的最小生成树问题,并设计了相应的求解算法,给出了数值例示。     

图的m-距离染色

图的染色问题具有广泛的实际应用背景,其与计算机网络结构、银行安全密码、电信通讯站点的频率分配以及人力资源配置等问题均有重要的联系。作为图的正常染色的自然推广,学者们提出了图的强染色（即2-距离染色）乃至 m -距离（m为正整数）染色的概念。文章在此基础上,定义了有向图的 m -距离染色,并研究了无向图和有向图的 m -距离染色问题,运用图论的相关技巧及标号排序等方法获得了圈、树、路、星图、有向圈、有向树的 m -距离色数,及一般无向图和有向图其 m -距离色数的上、下界。     

Table Operation Method for Optimal Spanning Tree Problem

1.INTRODUCTIONSeveraloptimalspanningtreemethodshavebeendevelopedfortheweightundirectedgraph.ThecommonlyusedmethodsareKruskal'sMethod[4](alsocalledGreedyAlgoritlun)andDisorderAlgorithm[4j.Asfortheweightdigraph,littleworkhasbeendone.Inthepractice,thecomplicateddigraphisdifficulttodepict,butitiseasytobeexpressedintheformofatable.Basedoilthetableexpressioninsteadofthedigraphexpression,thispaperdevelopsanoptimalspanningrooted-treemethodcalledtableoperationsmethod(TOM).2.SOMEBASICCONCE…     

正则有向自补图的一种构造方法

现实生活中,计算机网络,交通运输网都可以用图的方法来表示,对网络的构建模型研究,网络的各种参数的研究都可以用关于图的构造方法和图的各种参数来实现,因而对满足某一性质图的构造方法的研究在理论和实际上是有意义的,自补图是一类十分重要的图,它在结构上具有对称性,本文利用的构造的方法,给出了一种构造为2n 1的正则有向自补图的方法。     

关于四个两两无交有向图n·_3之并的优美性

文章中证实了四个两两无交有向图n·C 3之并的优美性及两两无交有向图n·C 3,n·C 3,2n·C 3之并的优美性,标号设计采用了对顶头数n分段设计方法.     

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…     

有向图2Cn的优美性

图论是数学的一个分支,特别是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是在计算机科学中有着非常广泛的应用。图的标号问题是图论中极有趣的一个研究课题,有着较好的研究价值和广阔的应用背景。图的一个顶点标号是顶点集合到非负整数集合的映射,而边标号是边集合到非负整数集合的映射,根据对映射的不同要求,产生了各种各样的图的标号问题,有向图的优美标号是其中的一类。用Cn表示有n个顶点的有向圈,mCn表示m个无公共顶点的有向圈Cn之并,本文研究了有向图mCn的优美性,利用搜索图的标号的算法与数学证明相结合的方法,证实了有向图2Cn为优美图,其中n为任意正整数。