若干优美和边魔幻标号算法及其应用研究

论文摘要

图的标号作为图论学科研究的一个分支,在1966年由Rosa等人提出,目的是解决Ringel的猜想。图的标号是图的顶点集和边集到整数集的映射,根据对边标号的不同要求,产生了各种类型的标号,比如:优美标号、奇优美标号、幸福标号、奇优雅标号和边魔幻标号等。由于图的标号在复杂网络、大数据、计算机理论、运筹学、有机化学、系统科学和图形密码等众多领域中有着广泛的应用,许多研究者在此方面作了大量的工作,但标号中仍然有很多问题没有解决。一些猜想至今没有被证明或否定,例如所有的树都是优美的,所有的树都是魔幻的,所有的树都是奇优美的等猜想。现已有的文献中对图的标号研究都是将图形用数学公式刻画出来,然后用组合构造的方法证明该图具有标号,由于对随机图的难以描述,所以主要研究的是容易刻画的特殊图或某一类图,比如毛毛虫树、对虾树、星图、扇图、轮图、圈图、联图等。而这种研究方法几乎是试探性的手段,即在大量的极为特殊的例子中寻找标号的规律,从而找到证明的路径。这种方法的工作量大,内容繁琐,模型特殊,算法效率低,灵活性差,所以没有办法证明一般简单连通图是否具有标号。本文用计算机的算法解决随机图的标号问题,利用图的生成算法生成所需的非同构图库,通过分析若干优美标号和边魔幻标号的约束条件和相应的标号特点,计算对应的取值空间,设计标号算法。将得到的标号算法应用于图形密码中来解决现实中的问题,本文的主要研究工作如下:(1)介绍图的相关概念,现有图形密码的认证方案,边魔幻全标号的已有结论。(2)设计并实现了层次级联图的若干优美标号算法。首先证明了层次级联图所具有的性质,用组合构造的方法证明和算法实现层次级联图具有集有序优美标号。其次以层次级联图为基础图,通过给每个顶点加一个叶子形成的图,证明和算法实现该图具有强优美标号。最后以层次级联图为基础图,通过给每个顶点任意加叶子点形成的图,证明和算法实现该图具有奇优美标号。(3)设计并实现了图的边魔幻全标号算法。主要有两个算法,其中一个为随机图的超级边魔幻全标号算法,目前可以实现对9个点以内所有随机图的超级边魔幻性判断,得到超级边魔幻图、非超级边魔幻图,并总结分析算法实验结果得出定理:9个点内的所有树图是超级边魔幻图和9个点内其它图的相关结论。另一个是树图、单圈图和双圈图的边魔幻全标号算法,目前可以实现对10个点内树图、单圈图和双圈图的边魔幻性判断,总结分析算法实验结果得出定理:10个点内的所有树图是边魔幻图,10个点内的所有单圈图是边魔幻图,10个点内的所有双圈图是边魔幻图。(4)利用人们对于图形的易记性和基于上述已有的图标号算法,将图标号应用于新型图形密码中,提出一种图形加标号算法的解锁方案,并对其进行可行性分析。

论文目录

• 摘要
• Abstract
• 1 绪论
•   1.1 引言
•   1.2 研究背景、目的及意义
•   1.3 本文的主要工作
•   1.4 本文的组织结构
• 2 图标号的相关理论和图形密码的认证方案
•   2.1 引言
•   2.2 图标号的相关理论
•   2.3 图形密码的认证方案
•     2.3.1 基于识别型的图形密码方案
•     2.3.2 基于线索回忆型的图形密码方案
•     2.3.3 基于回忆型的图形密码方案
•   2.4 本章小结
• 3 层次级联图的若干优美标号算法
•   3.1 引言
•   3.2 优美标号和层次级联图的相关定义
•   3.3 层次级联图的特殊性质
•     3.3.1 数学归纳法证明层次级联图的特殊性质
•     3.3.2 结果示例图
•   3.4 层次级联图的集有序优美标号算法
•     3.4.1 组合构造法证明层次级联图的集有序优美标号
•     3.4.2 算法描述
•     3.4.3 结果示例
•   3.5 以层次级联图为基础的扩展图的强优美标号算法
•     3.5.1 组合构造法证明扩展图的强优美标号
•     3.5.2 算法描述
•     3.5.3 结果示例
•   3.6 以层次级联图为基础的变形图的奇优美标号算法
•     3.6.1 组合构造法证明变形图的奇优美标号
•     3.6.2 算法描述
•     3.6.3 结果示例
•   3.7 本章小结
• 4 图的边魔幻全标号算法
•   4.1 引言
•   4.2 边魔幻全标号的相关定义
•   4.3 随机图的超级边魔幻全标号算法
•     4.3.1 算法设计
•     4.3.2 算法描述及流程图
•     4.3.3 算法分析
•     4.3.4 算法示例
•     4.3.5 相关结论和猜想
•   4.4 树图、单圈图和双圈图的边魔幻全标号算法
•     4.4.1 算法设计
•     4.4.2 算法描述及流程图
•     4.4.3 算法示例
•     4.4.4 相关结论和猜想
•   4.5 本章小结
• 5 若干优美和边魔幻标号算法在新型图形码中的应用
•   5.1 引言
•   5.2 GLAUP图形密码方案
•     5.2.1 GLAUP图形密码方案设计思路
•     5.2.2 GLAUP图形密码方案实现
•   5.3 GLAUP图形密码方案性能指标研究
•     5.3.1 用户测试方案
•     5.3.2 收集测试数据并建模
•   5.4 GLAUP方案测试结果评估
•     5.4.1 可用性评估
•     5.4.2 安全性评估
•   5.5 总结
• 结论
• 致谢
• 参考文献
• 附录A 一个图的超级边魔幻全标号程序运行过程图集
• 附录B 9个点内的部分超级边魔幻图的实验结果集
• 附录C 单圈图和双圈图的部分边魔幻图的实验结果集
• 攻读学位期间的研究成果

文章来源

类型: 硕士论文

作者: 王露露

导师: 李敬文

关键词: 层次级联图,优美标号,超级边魔幻全标号,边魔幻全标号,图形密码

来源: 兰州交通大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 兰州交通大学

分类号: O157.5

DOI: 10.27205/d.cnki.gltec.2019.000599

总页数: 82

文件大小: 2276K

下载量: 8