论文部分内容阅读
图论是计算机与组合数学的重要组成部分,它以图为研究对象,在计算机理论、运筹学和机器学习等方面有着重要的研究价值。现在,计算机的发展已经成为推动各个学科发展的重要动力,由此,计算机的出现也大大推动了图论的发展。图标号起源于Rosa提出的优美猜想,是图论中的一个重要分支,并且具有广泛的使用价值。现实生活中的许多问题都可以抽象为图标号问题,通过对图标号进行理论分析,从而解决相关的问题。图标号种类较多,其中研究较为广泛的标号问题有优美标号、幻类型标号、幸福标号。幻类型标号中边幻和全标号和点幻和全标号研究较多,但是传统的研究方法多采用组合构造法,只能对结构确定、有规律的图进行证明。由于传统的组合构造法的局限性,并不能给出随机图的相关结论,为了对图的边幻和性进行全面研究,本文借助计算机的高运算能力以及优化边幻和全标号的传统解空间的措施,采用了递归回溯的方法,设计了边幻和全标号算法。对9个点内的所有简单连通图进行了边幻和全标号验证,得到了9个点以内所有连通图的边幻和全标号情况。由于随着点数和边数的增加,连通图的数量呈指数级增长,并且由于解空间较为庞大,故选取17个点以内的所有树图、16个点以内的所有单圈图和15个点以内的所有双圈图进行边幻和全标号验证。将实验结果整理后分析,得出了有限点内的相关定理并提出了相应的猜测,基于这些猜测,再对大点数的图进行验证,判断猜测是否成立。对边幻和全标号算法进行改造,得到了边幻和全标号全解算法和边幻和全标号模糊匹配算法。利用这三种算法并结合正则表达式对目前提出的关于边幻和全标号的相关公开问题做了讨论,证明了其中一部分公开问题、对一部分公开问题给出了一定的证明思路并纠正了一部分公开问题。由于计算机只能得到有限点内的随机图的结论,不能对一类图做出判断,故利用组合构造法以及计算机的优势,定义了几类联图,利用边幻和全标号算法给出有限点以内的基础图形的所有解,再利用组合构造法给出这几类联图的数学证明,充分发挥了计算机和组合构造法的优势。边幻和全标号与(a,d)-边反幻和全标号之间存在一定的联系,借助于设计边幻和全标号算法的经验,设计了(a,d)-边反幻和全标号算法。由于(a,d)-边反幻和全标号的解空间太过于庞大,对11个点以内的所有树图进行d=1的(a,d)-边反幻和全标号验证,对6个点以内的所有图进行d=1、d=2和d=3的(a,d)-边反幻和全标号验证。根据所得的有限点以内的标号结果,证明了一些特殊图在不同d的情况下的(a,d)-边反幻和全标号。