图的L(2，1)-标号问题源于无线电发射台的频率分配问题，频率分配问题最早是1980年由Hale在文献[5]中提出的.Gerard J.Chang和David Kuo于1996年在文献[9]中更精确地提出图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.图的一个k-L(2，1)-标号是图的一个L(2，1)-标号，使得所有标号都小于等于k并且至少有一个取到λ.图G的L(2，1)-标号数，用λ(G)表示，是指最小的整数λ使得图G有一个k-L(2，1)-标号.　　Griggs和Yeh于1992年在文献[6]中给出了路Pn、圈Cn和轮Wn的L(2，1)-标号数的确切值:λ（P2)=2，λ（P3）=λ（P4）=3，λ（Pn）=4，n≥5，λ(Cn)=4，λ(Wn)=n+1;并证明了对于最大度△≥1的树T，λ(T)为△+1或△+2;他们证明了对于一般图的L(2，1)-标号问题是NP-完备问题.对于最大度为△的一般图G，Griggs和Yeh证明了λ(G)≤△2+2△，当图G是3-连通时，L(2，1)-标号数的上界可改进为λ(G)≤△2+2△-3;当图G的直径为2时，有λ(G)≤△2.在文献[6]中Griggs和Yeh还提出了关于L(2，1)-标号数λ(G)的猜想:对于最大度为△的一般图G，有λ(G)≤△2.　　1996年Gerard J.Chang和David Kuo在文献[9]中证明了对于最大度为△的一般图G，有λ(G)≤△2+△.Kral和Skrekovshi等[10]把上界改进为λ(G)≤△2+△-1.2008年Goncalves在文献[12]中把上界改进到λ(G)≤△2+△-2.　　对于Halin图现有的主要研究结论有:其L(p，q)-标号数λ1(G;p,q)≤(2q-1)△(G)+6p-3，λd(G)≤△+3(2d-1)，λ(G)≤3△+9,λ(G)≤3△+3等.　　本文结合Floyd算法、贪心算法和遗传算法提出了一种求解图的L(2，1)-标号的混合遗传算法，用这种算法能以极快的收敛速度给出一般图的L(2，1)-标号的近似解，并用算法对理论结果进行验证，两者的结果基本是吻合的，无论是实验结果和理论结论都理想的.　　论文的主要内容集中在第二到五章:　　第二章中主要研究了Halin图的L(2，1)-标号问题，得到的主要结论:对于最大度为△的Halin图G，λ(G)≤△+7.　　第三、四章主要讲述了基于遗传算法求解L(2，1)-标号问题的算法及其Matlab实现，该混合算法具有较快的收敛速度，能够快速地求解出图的L(2，1)-标号问题.　　第五章分析了混合遗传算法的实验结果，结果证明该算法的收敛速度极快，并且效果也很好，特别是对Halin图进行了实验验证，结果证明本文给出的上界还是比较理想的，另一方面理论结果也验证了算法的可靠性及可行性.