关于多状态边权网络最优路问题的研究

本文对于多状态边权网络最优路问题进行分析,并给出称号算法。     

仙人掌图的L（2，1）-标号

一个图G的L（2，1）-标号是给图G上的顶点分配非负整数标号，使得G上相邻的两个点的标号至少相差2，距离为2的两个点的标号则不同．G的L（2，1）-标号数λ（G）是所有能使图G正常标号的最小标号．如果一个图的任何两个圈不含有公共边，则称这个图为仙人掌图．显然树是它的一个子图类．对于任何树T，有△（T） ＋ 1 ≤λ（T） ≤△A（T）＋2．本文中我们证明了在一些条件下，这个界也适用于仙人掌图．     

随机图的邻点和可约边标号算法

如果对于一个点数为p,边数为q的图G(p,q),存在映射f:E(G)→{1,2,…,q},并且对于任意两个同度相邻点u,v存在Sum(u)=Sum(v),其中■,称f为图的邻点和可约边标号。在已有的点魔幻边标号和点可约边染色研究的基础上,结合实际应用,提出了邻点和可约边标号的新概念,并设计了邻点和可约边标号(adjacent vertex sum reducible edge labeling,AVSREL)算法。算法通过循环迭代寻优的方式,对图进行标号,得到了10个点内所有非同构图的标号结果,经过结果分析总结出若干定理并加以证明。     

图P3n的优美标号

定义了图Ｐ＾３ｎ,证明了当ｎ＝６ｋ＋２及ｎ＝６ｋ＋４时,图Ｐ＾３ｎ是优美图,并得到它们的优美标号,其中ｋ是任意自然数。     

关于图Cn+Kt的和谐性

本文证明了当n为奇数且(n,t+1)=1时，如果集合M={ni-1|i=1,2,…,t+1},N={(t+1)j|j=0,1,…,n-1}满足M∩N≠?时，图C_n+K_t是和谐图.从而推广了M.Keid的结果:C_n+K₂是和谐图.     

龙虾树的多级距离标号

连通图G的多级距离标号是指顶点集y(G)到{0,1,2,…}的一个映射f,它使得对于任意的u,u∈y(G)满足:|f(u) - f(v)|≥diam(G)+1-d(u,u),其中diam(G)是图G的直径,d(u,v)是两点u,u之间的距离.函数f的跨度是指max u,v∈V(G){f(u)-f(v)}.图G的多级距离数是指它的所有多级距离标号的最小跨度.本文研究了一类关于权中心点对称的龙虾树,并得出了它的多级距离数的一个下界,进而得出了它在某些特殊情况下的多级距离数的确切值.     

不含4,5,6-圈的平面图的L(p,q)-标号

证明了若G为不含4,5,6-圈的平面图,则λp,q(G)≤(2q- 1)Δ(G)+6p+6q-6.这一结果暗含着对于△(G)≥12且不含4,5,6-圈的平面图G,x(G2)≤[3Δ(G)/2]+1成立.因此对于这样一类图部分地证实了Wegner猜想.     

图的填充和运算

建立了图的局部最优填充定理,并研究结合图的填充数。最后给出了图的局部最优填充定理的一个应用。     

图的min-max型最优消去顺序问题

文[1]从算法复杂性的估计中提出一个图的最优标号(排序)问题-顶点的最优消去问题.本文将给出若干基本的理论结果,其中包含NP-完全性、上下界、与其它目论参数的关系及特殊图结果等.     

关于等高k-毛虫树的带宽

图的带宽问题是图论的一个重要课题。然而 ,即使对毛长不等的单毛虫树 ,其带宽问题也是NP_完全的。利用Chv偄ｔａｌ的直径型带宽下界为工具 ,我们可以确定等高k_毛虫树的带宽