用边标号法解决交通网络连通性问题

提出了一种新的网络连通性表达法，称为“边标号法”，从算法的角度解决了增设虚拟边网络连通性表达法和对偶图网络连通性表达法所带来的大量工作量问题，在对交通网络图不作任何修改的情况下，清楚而有效地表达出网络的连通特性，体现出了边标号法的优越性，并用一个具体实例通过程序实现了该方法。

探讨斐波纳契毛毛虫树的边标号

为了探讨斐波纳契毛毛虫树的边标号,采用不同于原定义的图标号的方法 -先从边对每个图进行标号。利用先从边标号的特点,主要讨论了1-斐波纳契毛毛虫树的边二分奇优美标号,边优美标号及边魔幻全标号。最后讨论了1-斐波纳契毛毛虫超级同构图的二分奇优美标号。这样的方法省去了大量繁复工作,大大提高了图标号的效率。

圈的超边优美标号

1994年,Mitchem和Simoson在研究标号图的问题时,提出了超边优美图的概念。在随后的研究过程中,一些图被证明具有超边优美性质,同时关于超边优美图的一些猜想也被提出。讨论了圈Cn的超边优美性,证明了当n≠4,6时,圈是超边优美的。

不超过7阶的3-关系图的刻画

给定一个图G,如果存在一个边标号树T,使得树T的叶子集等于图G的顶点集,并且树T任何叶子x到叶子y的唯一路径上的边标号之和为3当且仅当xy为图G的边,那么称图G是一个3-关系图.该文讨论了什么样的图是3-关系图,证明了图G是3-关系图的必要条件为图G是二部图,即只要图G包含奇圈,则图G不是3-关系图.更进一步,完全刻画了圈为3-关系图的充要条件,即一个圈是3-关系图当且仅当圈为偶圈,并且给出了偶圈相对应的边标号树.最后讨论了比较小的图为3-关系图的条件,即证明了阶至多为7的图是3-关系图的充分必要条件为图G是二部图.

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

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

P_(2r+1,2m+1)图的一个优美标号

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

若干特殊图及其联图的邻点可约边标号算法

设G(V,E)是一个简单图,若存在一一映射f:E(G)→{1,2,…,|E|},使得对任意两点uv∈E(G),如果d(u)=d(v),有S(u)=S(v),其中S(u)=∑uω∈E(G)∫(uω),d(u)表示点u的度,则称f为G的邻点可约边标号(adjacent vertex reducible edge labeling,AVREL)。在已有图标号概念与可约染色概念的基础之上,结合实际问题提出了邻点可约边标号新概念,并设计了一种新的邻点可约边标号算法(简称AVREL算法)。该算法对边初始标号,然后针对邻点可约边标号的解空间进行递归搜索,最终筛选出满足边标号的图集并以标号矩阵的形式输出。经过对算法结果分析,总结出若干路图、扇图、星图、轮图、树图等特殊图及其联图在不同情况下的邻点可约边标号定理,并给出了证明。

图nC4的平衡标号

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

一类蜘蛛树的(k,d)-优美标号

(k,d)-优美标号因为参数k,d可以取很多值,从而使得一些优美图是(k,d)-优美标号的特例.本文给出了(k,d)-优美标号的概念,定义了T(n+1,m)-蜘蛛树,并证明了T(n+1,m)-蜘蛛树不同情形下的(k,d)-优美标号.

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

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

P_(5,4m)的优美性

设u,v是两个固定顶点,用b条内部互不相交且长度均为a的道路连接u、v所得到的图用Pa,b表示。Kathiresan证实P2r,2m-1(r,m均为任意正整数)是优美的,且猜想:除了(a,b)=(2r+1,4s+2)外,所有的Pa,b都是优美的。杨元生已证实P2r+1,2m-1是优美的,本文证明m=2n(2l-1),(0≤n≤4,l∈N)时,P5,4m是优美图。

一类优美图

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

圈的优美性

本文得到了圈Ｃｎ为优美图的充要条件，并给出了圈Ｃ４ｋ，Ｃ４ｋ－１的优美标号。

非树序列图的充要条件

为处理纠错码问题提供理论基础,使用映射分析、副对角线和邻接矩阵分析的方法,使用"点包"和"1-半副对角线"的概念,获得下列结果:点数大于边数的非树简单图不是序列图;点边数相等的序列图的充要条件;非树序列图的充要条件,及非树序列图有连续的序列标号的充要条件;还给出了方阵的副对角线及半副对角线的结构。这些结果可以用来构造序列图,判别序列图,寻找序列图的序列标号,在通信、军事编码等领域有较大的应用价值。

P_(3,4m)的优美性

设u、v是两个固定顶点,用b条内部互不相交且长度均为a的道路连接u、v所得到的图用Pa,b表示。Kathiresan证实P2r,2m-1(r,m均为任意正整数)是优美的,且猜想:除了(a,b)=(2r+1,4s+2)外,所有的Pa,b都是优美的。杨元生已证实P2r+1,2m-1是优美的。本文证明P3,4m是优美图,从而当a=3时Kathiresan猜想成立。

图类{K^(*)_(2)P_(n)+2e}的边-平衡指数集

研究了特殊图类的边的标号问题,根据字典乘积图概念定义了{K^(*)_(2)P_(n)+2 e}这种特殊图类,并利用图结构的分解和边标号互换的方法给出了该图类的平衡指数集的准确值和证明。

一类蜘蛛树T2n的强优美性

用T2n表示有2n点的树,给出了T2n优美,强优美性.

几类特殊图的一般指标集

令G=(V(G),E(G))为一简单连通图,V(G)和E(G)分别是图G的顶点集和边集。一个顶点标号函数f:V(G)→Z_(2)诱导出一个边标号函数f^(*):E(G)→Z_(2),其中v_(1)v_(2)∈E(G),有f^(*)(v_(1)v_(2))=f(v_(1))+f(v_(2))。当标1和标0的顶点数相差m(m<|V(G)|)时,标号为1和0的边数差的集合称为图G的一般指标集。给出圈、路和C_(n)×P_(2)的一般指标集。

2类非连通图的优美性

本文利用构造法,研究了2类非连通图图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1的优美性.证明了下面的结论:设m为任意的正整数,Gm-1是表示边数为m-1的优美图,则当m≥2时,图m·C3∪Gm-1及m·(P2∨K2—)∪Gm-1都是优美图.其中,C3是表示三个顶点的回路图,P2∨K2—是两个顶点的路P2与两个孤立顶点的图K2—的联图,m·C3是m个图C3恰有一个公共点的图,m·(P2∨K2—)是m个图P2∨K2—恰有一个公共点的图,G∪Gm-1是把图G与Gm-1不相交并起来所得的非连通图.

P_(2r,4m+2)图(r=8,10)的优美性

设u、v是两个固定顶点,用b条内部互不相交且长度皆为a的道路连接u、v所得的图用Pa,b表示.K.M.Kathiresan证实P2r,2m-1(r,m皆为任意正整数)是优美的,且猜想:除了(a,b)=(2r-1,4m-2)外,所有的Pa,b都是优美的.杨元生教授已证实P2r-1,2m-1是优美的,并且证实了当r=1,2,3,4,5,6,7,9时P2r,2m也是优美的.该文证实当r=8,10时P2r,4m+2也是优美的.