分派问题一种标号算法

文章采用一定技巧,把求最短路的Ｄｉｊｋｓｔｒａ算法用于求解分派问题,得到一种标号算法,计算复杂性仅为Ｏ（ｎ２）,比以往的算法减少了一个数量阶Ｏ（ｎ）。     

交通网络连通性表达法的研究

通过对增设虚拟边网络连通性表达法和对偶图网络连通性表达法的描述和它们所面临问题的分析研究,说明这两种方法在交通网络连通性表达上,尤其是在引进交通转弯限制时所显示出来的需要大量处理工作的问题,提出了一种新的网络连通性表达法,作者称为“边标号法”,此法避免了对交通网络增设虚拟边或进行点边转化所带来的大量工作量问题,在对交通网络图不作任何修改的情况下,清楚而有效地表达出网络的连通特性。并用一个具体实例通过程序实现该方法,体现出了边标号法的优越性     

一类优美图

设u、ν是两个固定顶点.用b条内部互不相交且长度皆为a的道路连接u、ν所得的图用P_a,b表示.KM.Kathiresan证实P_2,2m-1(r,m皆为任意正整数)是优美的,且猜想:除了(a,b)=(2r+1,4s+2)外,所有的P_a,b都是优美的.杨元生已证实P_2r+1,2m-1是优美的,并且证实了当r=1,2,3,4时的P_2r,2m也是优美的.本文证实r=5,6,7时P_{2r,2m相似文献}   

一类图优美性的证明

本文给出一种 GL 阵的概念,把若干 GL 阵进行各种运算,所得的 GL 阵对应的图是优美的。从而得到为数众多的一类图,如放射树等,都是优美图。在[2][3]和[4]中,利用 GL 阵还证明了优美图 Bodendiek 猜想及其一种推广。     

非连通图G1∪G2及G1∪G2∪K2的优美性

将k-优美图的概念进行了推广，引入了k-l优美图及标号间距的概念，并以此为基础，分别推出了一般情形下判定非连通图G1∪G2及G1∪G2∪K2是优美图的两个充分条件；同时得出了图（C3VK^-n）∪st（m）∪K2是优美图，其中k、l为自然数，l〈k，C3是长为3的圈，Kn为n个顶点的完全图，K^-n是Kn的补图，St（m）表示m＋1个顶点的星形树，C3VK^-n是C3与K^-n的联图．     

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

证实了 ,两个无交有向图 n.C 3之两个相邻 2度点处反方向粘合的优美性 .由于在设计优美标号时 ,缺乏规律性 .从而采用了对顶点数 n,分段设计标号的方法 .     

关于图C_n(a_1,a_2,…,a_n)的整数幻谱

一般没有有效的方法得到图G的幻谱.本文给出了一种整数幻谱的分析方法,讨论了图Cn(a1,a2,…,an)的整数幻谱问题,得到Cn(1,3,…,2n-1)与Cn(2,4,…,2n)等4类图的整数幻谱及一些新的结果.     

图P2r,2m的优美标号

设u,v是两个固定顶点,用b条内部互不相交且长度皆为a的道路连接u,v所得图用P_(a,b)表示．K．M．Kathiresan证明：P_(2r,2m-1)(r,m皆为任意正整数)是优美的,且猜想,除了(a,b)=(2r 1,4s 2)外,所有的P_(a,b)都是优美的．杨元生已证明P_(2r 1,2m-1)是优美的,并且证明了,当r=1,2,3,4,5,6,7时,P_(2r,2m)也是优美的．作者证明：r为任意奇数时,P_(2r,2m)也是优美的．     

广义指派问题及其在军事装备运输中的推广应用

军事装备中的运输问题复杂多样,如何建立数学模型是寻求优化方案的关键.本文首先将最优线性指派模型推广到广义指派模型并给出其两种算法,其次对带有时间约束的运输问题进行建模,并设法将其转化为广义指派问题来处理,从而为这类运输问题提供了一种有效可行的算法.     

关于图的距离标号问题

图G的L（2，1）-标号是一个从顶点V（G）集到非负整数集的函数f（x），使得若d（x，y）：1，则｜f（x）-f（y）｜≥2；若d（x，y）=2，则｜f（x）-f（y）｜≥1。图G的L（2，1）-标号数A（G）是使得G有max{f（v）：v∈V（G）}=k的L（2，1）-标号中的最小数愚。本文将L（2，1）-标号问题推广到更一般的情形即L（d1，d2，d3）-标号问题，并得出了复合图的λd1，d2，d3（G）的上界。