随机图的幻和反幻算法研究

发布时间：2022-07-13 09:41

　　图论是计算机与组合数学的重要组成部分,它以图为研究对象,在计算机理论、运筹学和机器学习等方面有着重要的研究价值。现在,计算机的发展已经成为推动各个学科发展的重要动力,由此,计算机的出现也大大推动了图论的发展。图标号起源于Rosa提出的优美猜想,是图论中的一个重要分支,并且具有广泛的使用价值。现实生活中的许多问题都可以抽象为图标号问题,通过对图标号进行理论分析,从而解决相关的问题。图标号种类较多,其中研究较为广泛的标号问题有优美标号、幻类型标号、幸福标号。幻类型标号中边幻和全标号和点幻和全标号研究较多,但是传统的研究方法多采用组合构造法,只能对结构确定、有规律的图进行证明。由于传统的组合构造法的局限性,并不能给出随机图的相关结论,为了对图的边幻和性进行全面研究,本文借助计算机的高运算能力以及优化边幻和全标号的传统解空间的措施,采用了递归回溯的方法,设计了边幻和全标号算法。对9个点内的所有简单连通图进行了边幻和全标号验证,得到了9个点以内所有连通图的边幻和全标号情况。由于随着点数和边数的增加,连通图的数量呈指数级增长,并且由于解空间较为庞大,故选取17个点以内的所有树图、16个点以内的所有... 

【文章页数】：101 页

【学位级别】：硕士

【文章目录】：
摘要
Abstract
1 绪论
    1.1 选题背景及意义
    1.2 国内外研究现状
    1.3 主要研究内容
    1.4 论文组织结构
2 图基础理论概述
    2.1 图的基础理论
    2.2 图标号相关概念
    2.3 标号研究现状
    2.4 本章小结
3 边幻和全标号
    3.1 算法设计
        3.1.1 边幻和全标号的传统空间
        3.1.2 边幻和全标号的优化空间
        3.1.3 边幻和全标号空间对比
        3.1.4 边幻和全标号的预判函数
        3.1.5 边幻和全标号算法描述
    3.2 算法示例
    3.3 算法分析
    3.4 算法结果与猜想
        3.4.1 9个点以内所有非同构图
        3.4.2 17个点以内所有树图
        3.4.3 16个点以内所有单圈图
        3.4.4 15个点以内所有双圈图
    3.5 本章小结
4 边幻和全标号的公开问题解决
    4.1 边幻和全标号全解算法
    4.2 边幻和全标号模糊匹配算法
        4.2.1 预测序列预处理
        4.2.2 边幻和全标号模糊匹配算法描述
    4.3 算法示例
    4.4 公开问题讨论
    4.5 一些联图的证明
    4.6 本章小结
5 a,d-边反幻和全标号
    5.1 a,d-边反幻和全标号解空间
    5.2 算法设计
    5.3 算法示例
    5.4 算法分析
    5.5 算法结果
        5.5.1 有限点以内的(a,d)-边反幻全标号算法结果
        5.5.2 特殊图的(a,d)-边反幻全标号
    5.6 本章小结
结论
致谢
参考文献
攻读学位期间的研究成果
附录A 各程序运行截图及说明



本文编号：3659812