论文部分内容阅读
图的标号问题是图论中具有实际应用背景的研究课题.近年来,国内外这方面的研究比较活跃,研究成果被应用于射电天文学、X-射线衍射晶体学、密码学、通讯网络编址、导弹控制码设计、同步机码设计、无线电频道分配和读取DNA序列等.它的研究始于1966年A.Rosa的著名的优美树猜想.一个图的顶点标号是图的顶点集到整数集(一般的也可以是一个交换群)的映射,而边标号则是图的边集到整数集的映射.由于新的应用背景的不断出现产生了一些新的标号及公开问题,这些标号的构造方法和理论有待于进一步研究.这些研究有重要的理论意义和应用价值.
本文利用已有的搜索图的标号的算法,将计算机构造性证明与数学证明相结合,主要研究了具有一个公共边的n个长为m的有向圈(C)m的并所构成的有向图n-(C)m的优美标号问题.
1991年,马克杰证明了:当n为偶数时,有向图n-(C)3为优美图.2008年,赵凌琪等人证明了:当n为偶数,m=5,7,9,11,13时n-(C)m是优美的;并提出猜想:当n为偶数时,对任意正整数m≥14,n-(C)m是优美的.2009年,徐喜荣等人证明了:当n为偶数且m=4,6,8,10时,n-(C)m是优美的.
本文在第二章,第三章中分别证明了当m=17,19和m=21时此猜想成立.