论文部分内容阅读
图论是数学的一个分支,特别是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是在计算机科学中有非常广泛的应用.
图的标号问题是图论中极有趣的一个研究课题,有着较好的研究价值和广阔的应用前景.它的研究始于1966年A.Rosa的著名的优美树猜想.一个图的顶点标号是图的顶点集到整数集(一般的也可以是一个交换群)的映射,而边标号则是图的边集到整数集的映射.根据对映射的不同的要求,产生了各种各样的图的标号问题.
本文利用已有的搜索图的标号的算法,将计算机构造性证明与数学证明相结合,主要研究了具有一个公共顶点的,n个长为m的有向圈Cm的并所构成的有向图n·Cm的优美标号的问题.1994年,杜之亭等人提出猜想:当n为偶数且m为奇数时,有向图n·Cm为优美图.本文在第二章和第三章中分别证明了当m=21和m=23时此猜想成立.并在第四章给出此猜想的完整的证明.