树的二分全优美标号

一个有q边的连通图G的一个标号是一个映射f,使得图G顶点分配给不同的整数,如果图G的所有边标号集等于{1,2,…,q},则称f是图G的一个优美标号,称G是优美图.图的优美标号可用于解决Rosa分解猜想,这就需要证明每一棵树是优美的,然而它又成为一个未解决的难题.已知树的二分全优美标号可得到一些逼近优美树猜想的结果,因此可考虑一个弱于优美树猜想的猜想:一棵被删除所有叶子后余图恰是一棵毛毛虫树的树T是二分全优美的.树T的一个二分标号是一个双射f,且存在一个正整数k,使得f(u)≤k≤f(v),则顶点u和v属于树T的顶点集的二部分划分的不同部集.定义了全优美标号空间和k?二分全优美树,证明了一类二分全优美树,给出一些大型二分全优美树的构造方法.     

关于算术图的几个结果

图G=(V，E)(其中q=|(E(G)|称为(k，d)-算术图如果不同的点能用不同的非负整数标号，使得由端点标号之和所得边的值构成序列k，k d，k 2d，…，k (q-1)d．本文我们对(k，d)-算术图进行了讨论，得到了(k，d)-算术图的几个结果．     

转向约束网络中的对偶最短路径树原理及其原型算法

为比较有无转向约束条件下最短路径特征及其搜索算法的异同点,基于对偶图理论证明了转向约束网络中从单个源点到所有弧的最短路径集构成其对偶网络的生成树,提出了对偶最短路径树(DSPT)概念,并利用其分析算法之间的关系。研究结果表明:转向约束下的现有求解方法包括弧标号算法、节点标号算法和对偶网络法都可以统一到DSPT算法框架内,而且与无转向约束的最短路径树(SPT)算法在路径搜索策略上是相同的;对于转向约束网络中的最短路径问题可建立一个DSPT原型算法,结合各种SPT标号技术能设计出更多的有效算法。     

关于图的L(2,1)-标号问题

图的L(2，1)—标号问题来自频率分配问题并且是NP—完全性问题。得到：(Ⅰ)G是p个顶点的简单图，对正整数k≥3，当p≥2k^2和△≥p／k时，有L(G)≤△^2。(Ⅱ)△(G)表示图G的最大度，则L(G)≥△(G) 1。(Ⅲ)若V(G)可划分为独立集V1，V2，…，Vk，且V(G)=U^ki=1Vi及Vi∩Vj=Ф，i≠j，则L(G)≤p k-2。     

基于GA的动态时延受限多播路由算法

探讨了包交换计算机网络中，具有端到端时延限制的动态多播路由问题．提出了一种基于遗传算法(GA)的动态时延受限多播路由优化算法．当节点加入或退出时，算法先利用Dijkstra第k最短路径算法求出节点到源点的最短路径集，再用遗传算法搜索最小多播树，仿真试验表明该算法可以动态求得满足时延约束的最小多播树．     

零相关区序列的交织构造

用交织方法研究ZCZ序列集合的构造，提出了基于交织技术的ZCZ序列构造的新方法．对于给定的周期为L的最佳自相关序列a和正交矩阵峨，首先选择合适的移位序列，对序列a进行交织得到（L，N）-交织序列b；再用正交矩阵HN将交织序列b扩展为新的序列集，则该序列集就是所构造的ZCZ序列集．用该方法可以构造达到或接近理论界的具有大的零相关区的ZCZ序列集，并统一了三元、四相和多相ZCZ序列集构造方法。     

两类图的算术标号

对于一个（p，g）图G，如果存在一个v（G）到非负整数集N0的一个映射以称为顶点标号）满足：（1）f（u）≠f（v），其中u≠v，且u，v∈V，（c）；（2）{f（u）＋f（v）｜uv∈E（G））={k，k＋d，…，k＋（g-1）d），称图G为（k，d）-算术图。证明了图Fm．4是（d，2d）-算术图和图Fm．6是（d，3d）-算术图。     

圈Cn与树Tk生成的单圈图的优美性及其它标号

Cn∪Tk是由圈Cn与树Tk生成的单圈图,证明了当n=3,4,6时圈Cn与鞭炮树Tk生成的单圈图的优美性,以及给出了Tk分别为鞭炮树、毛毛虫时单圈图Cn∪Tk的一些其它标号：序列标号和调和标号。     

圈Cn与树Tκ生成的单圈图的优美性及其它标号

Cn∪Tκ是由圈Cn与树Tκ生成的单圈图,证明了n=3,4,6时圈Cn与鞭炮树Tκ生成的单圈的的优美性,以及给出了Tκ分别为鞭炮树、毛毛虫时单圈图Cn∪Tκ的一些其它标号:序列标号和调和标号.     

伪Halin-图的结构性质及其色性

对2-连通平面图G，f0为G的一个边界(一个圈)上无弦的面，且V(fo)上的顶点度至少为3．若去掉f0边界上的所有边后得到的图为除V(f0)中的点外，所有点的度不小于3的树T，则称G为一伪Halin-图，称G为Halln-图当且仅当所有V(f0)中的点的度为3．同时讨论了这类图的结构性质及其色性．     

基于交织最佳自相关序列的ZCZ序列设计

为了减少零相关区序列设计中对相关参数的限制,基于任意一个周期大于4的最佳自相关序列,运用交织技术和递归运算,提出了一类新型的接近最优零相关区序列集的构造方法.通过递归运算,在保持ZCZ (zero correlation zone) 序列集包含的序列数目不变的条件下,可以将序列长度和零相关区宽度成倍扩展.构造的ZCZ序列集接近理论界,可应用于准同步CDMA (code division multiple access) 通信系统,消除共道干扰,提高通信质量.      

与任意图(m,r)-正交的(g,f)-因子分解

设G是一个图,用y(G)和E(G)表示它的顶点集和边集,并设g(x)和f(x)是定义在V(G)上的两个整数值函数,且对C每个x∈V(G),有5/2r-1≤g(x)≤f(x),则图G的一个支撑子图,称为G的一个(g,f)-因子,如果对每个x∈V(G),有g(x)≤d,(x)≤f(x)．图G的(g,f)-因子分解是指E(G)能划分成边不交的(g,f)-因子,设F=|F1,F2,…,Fm|和H分别是图G的因子分解和子图,若对所有1≤i≤m有|E(H)∩E(Fi)|=r,则称,和H(m,r)-正交．本文证明：若G是一个(mg m-1,mf-m 1)-图,H是G中任一有mr条边的子图,则G有一个(g,f)-因子分解与H(m,r)-正交。     

置换与优美树谱

研究置换与优美树的关系，得到在ｎ阶标号优美树集成（ｎ－２）阶优美置换的 了集之间存在着一一对应的结论。依据这一结论构造出ｎ阶优美树谱。     

矢值序列空间ss（E）的局部完全k-凸

刻划了赋序列范数的矢值序列空间ss(E)的局部完全k-凸性，证明了若ss是局部一致凸的，则ss(E)是局部完全k-凸的，当且仅当E是局部完全k-凸的．     

基于二次跳时序列的UWB无线电通信系统性能

讨论了扩展二次跳时序列和一般二次跳时序列及其特殊形式序列的构造，比较了它们的汉明互相关特性．在此基础上，比较了在PPM调制方式下基于这几类二次跳时序列的UWB系统的误码率，并给出了数值结果．研究结果表明，这几类二次跳时序列系统误码率相当一致，但一般二次跳时序列集具有更多的序列数目．     

太阳集上的最佳同时逼近的特征

讨论了太阳集上最佳同时逼近的特征。利用Kolmogorov条件和单侧Gateaux导数给出太阳集上最佳l_^1同时逼近的两个特征定理，且进一步得出G是太阳集等价于g0是G对χ1,χ2的最佳l_^1同时逼近→←g0和χ1,χ2关于G满足Kolmogorov条件。     

几种笛卡尔积图的集合边染色

图G的一个集合边染色是边集E(G)到集合X中的非空子集的一个映射f,并且满足对图G中任意两条相邻的边e_1,e_2,有f(e_1)≠f(e_2)且f(e_1)∩f(e_2)≠?,将集合X中的最小长度称为图G的集合边色数.通过引进集合矩阵,并利用构造染色矩阵的方法,得到了圈与路、路与路、圈与圈的笛卡尔积图的集合边色数.     

关于图邻点可区别上界的一点注

设G为一简单连通图．它的一个正常全染色叫做一个邻点可区别的全染色．如果满足：对G的任意两个顶点u，v，都有染点u以及与u相连的边所形成的色集与染点v以及与v相连的边所形成的色集不同．如果一个邻点可区别的全染色需要的色数为k，则把这个染色叫做k—邻点可区别的全染色(简记为k—AVDTC)．对图G，记x′α(G)=min{k|G有一个k—AVDTC}，称x′α(G)为图G的邻点可区别的全色数．本文给出了邻点可区别的全色数的一个上界．     

直径为5的树的优美性

本文利用移边定理（引理1）,对星型树进行移边操作,针对不同情况,得到了相应特殊标号点分布的双星型树,再技巧性地移边,最终得到一组具体的优美标号,证明了任一直径为5的树的优美性．     

���·�����㷨�ڽ�ͨ�����е�Ӧ��

拍卖算法是由Bertsekas教授提出的一种求解有向网络图最短路径的新算法，已经发展成为求解线性网络流问题的综合算法。应用分析对比法进行研究．介绍了拍卖算法，分析了其特点，与常用的标号设定算法和标号修正算法进行了对比。最短路拍卖算法特别适合于并行计算和大规模稀疏网络的求解，符合现实路网的特点和交通分配的要求，并且便于程序化．通过各种途径对基本算法进行改进、加速，可使计算速度提高数倍。拍卖算法可以快速求出多个起点和一个终点以及一个起点和多个终点的情况，适应不同分配算法的需求。在交通分配中，只要根据需求选择不同的起点集和终点集即可，不必求得所有节点对之间的最短路，避免大量不必要的计算，大大节省计算时间，在交通领域具有广阔的应用前景。