用标号法实现单源最短路径问题的迪杰斯特（dijkstra）算法

最短路径问题（最低费用问题）广泛应用于计算机图论，数据结构，数据通信等领域。本文主要通过对迪杰斯特（djkstra）算法的分析和改进实现来应用贪心算法解决实际问题。     

图的标号问题的计算机算法

时至今日,寻找一个图是否有优美标号和序贯标号的充要条件的问题仍是开的。 实际中,寻找一个稍大一点的图的优美标号和序贯标号是一件困难的事。本文对这两件工作给出了一种统一的算法,使得我们利用电子计算机可解决:一、验证一个图是否有优美标号和序贯标号。二、若有,则给出所有的优美标号和序贯标号。 本文用BASIC语言给出了本算法的一个程序。     

图nC4的平衡标号

图nC4平衡的必要条件及n＝（m 1)^2 1时的平衡标号被给出。     

图的圈带宽和

图的圈带宽和问题即为求图G的一个在圈上的标号,并且使得边的总长尽可能地小,用BSc(G)表示.给出了BSc(G)的一个上界并讨论了BSc(G e)与BSc(G)的关系,其中eE(G).     

关于图2×Cn的标号

定义了图2×Cn,给出了该图的优美、奇优美及奇强协调标号算法.     

网格图的并图P(n_1,n_2,…,n_m)的奇优美性和奇强协调性

通过构造方法,给出了平面网格图的并图P(n1,n2,…,nm)的奇优美标号和奇强协调标号以及其k-优美标号和k-强协调标号.从而证明这类图是奇优美图和奇强协调图.     

一类优美图

设u、v是两个固定顶点，用b条内部互不相交且长度皆为a的道路连接u、v所得的图用Pa,b表示.K.M.Kathiresan证实P2r,2m-1（r,m毕为任意正整数）是优美的，且猜想：除了（a,b)=(24-1,4m-2）外。所有的Pa,b都是优美的。该文第二作者已证实P2r-1,2m-1是优美的，并且证实了当r≤7时的P2r,2m也是优美的。该文证实r=9时P2r,2m也是优美的。     

树的几种标号之间的关系

主要研究了树的优美标号,奇优美标号,(k,d)-优美标号,边魔幻全标号,反魔幻全标号,和谐标号及幸福标号之间的关系.     

M-回路网络的中心选址

研究含边不交回路网络的中心选址问题,给出了一个求其最小直径支撑树的破圈算法,由此得到求其中心的O(mn)阶算法,这里m是网络中含回路的个数。     

（m,n）——构形的侧廓

如所知，确定一般图的侧廓，已经被证明是一个ＮＰ－完备问题，对于（ｍ，ｎ）－构形，本文确定了其侧廓并给出了相应的最优称号。     

关于毛毛虫的优美问题

关于毛毛虫的优美问题有不同的解决方法,其中毛毛虫优美标号的逐步构造方法简便易行,然而,在文献中由于其证明有些漏洞而往往引起读者对这种方法的可靠性的怀疑,本文将补充这个漏洞.     

完全网络图的出边-平衡指数集

针对网络图标号问题,在无向图边-友好标号的基础上,提出了有向图出边-友好标号的概念.利用标号矩阵来研究网络图标号问题,并通过引入子矩阵设计、矩阵变换等方法技巧,确定了完全网络图的出边-平衡指数集.同时利用标号矩阵可以得到相应的标号网络图.     

一类单圈图的优美性和平衡性

设L为简单无向图G的一个顶点标号,L称为图G的优美标号,若L满足以下两条：（1）L为G的顶点集V到{0,1,2,…,｜EI｜}的一个单射;（2）由L’（e）=｜L（u）-L（v）｜（其中e=uv）决定的边标号L’是G的边集E到{1,2,…,｜EI｜}的一个双射．进一步,若存在正整数c,使得对每一个uv ∈ E（G）满足L（u）≤c〈L（v）或L（w）≤c〈L（u）,则称L为图G的平衡标号,其中c为平衡特征．主要研究一类单圈图的平衡性并给出相应的平衡标号及其特征．     

关于香蕉树的奇优美标号

在图论的研究中,图的标号问题是在二十世纪六十年代提出的 ,人们根据应用的需要提出了许多关于简单图的标号猜想.在猜想和实际应用中,涉及到最多的是树.Chen et al定义了香蕉树,在此讨论了该树的奇优美标号以及在一些情况下的伪优美标号.     

算术图的构造方法

本文给出了由简易算术图构造复杂算术图的一些方法，发现了许多典型图类的算术标号。     

一类联图的冠的序列标号

设K1TB是单点图K1和平衡树TB的联图，该文研究了K1TB的冠I（K1TB），证明了I（K1TB）是序列图。     

P2r+1,2m+1图的一个优美标号

利用函数构造的方法得到所有P2r+1,2m+1图的一个优美标号.     

两类图的序列性

图G的标号指f是V(G)到整数集合的一个映射,然后边xy∈E(G)由f(x),f(y)导出标号.本文利用一类具有序列平衡标号的树的性质,通过"连结"与"粘接"方式,构造更多顶点的序列树;证明了C2n+1∨Km是序列图.     

关于图的算术标号

一个（p,q）-图G称为是（k,d）-算术的,若它的顶点可标以不同非负整数,使得它的边的赋值（由它的端点标号之和得到）能排成算术级数k,k＋d,k＋2d,…,k＋（q-1）d.本文综述了算术图的有关结果.