随机图的优雅算法及其在QR码防伪中的应用研究

论文摘要

图论是一个相对古老的数学分支,它是应用数学的一部分。在历史上图论曾经被多位数学家各自独立地建立过。关于图论的文字记载最早出现在欧拉（Leornhard Euler）1736年的论著中,他利用图论的方法解决了柯尼斯堡（Konigsberg）问题。由此,图论诞生,欧拉也被公认为图论的创始人。在随后的发展过程中,产生了许多著名的猜想,如汉密尔顿回路、四色猜想、优美树猜想等,现实中的许多问题都可以转化为图论的相关问题,从而引起了学者的注意和广泛研究,促进了多个学科的蓬勃发展。为了解决图论中的相关猜想,学者对图标号进行了广泛研究,图标号成为了当前图论中非常活跃的分支。图标号最早起源于1966年Rosa提出的优美树猜想:每一棵树都是优美树。虽然研究成果颇多,但该猜想至今未被解决。由此,图标号的研究广泛延伸,出现了多种类型的标号。优雅标号是图标号中的一种,也是本文主要研究的对象。它的概念于1981年被Chang、Hsu和Rogers首次提出,并给出了明确的定义。图标号广泛应用于计算机科学、网络、有机化学、机器学习等多个领域。由于图的数量随着点数的增大而递增,在未借助计算机之前,图的标号由手工操作,因而学者研究的范围比较单一,主要局限于特殊图或者某一类图,没有对图进行全局研究,对图的优雅性缺少全面认识。为了对图的优雅性进行全面研究,本文借助计算机高效率、长时间的处理能力,采用剪枝与预判函数相结合的方式,设计了递归回溯算法,对9个点内的所有简单连通图进行优雅性验证,得到9个点内所有优雅图和非优雅图。由于计算机硬件设备的配置有限,随着图形的增多,计算机处理时间加大,选取16个点内的树、单圈图、双圈图进行优雅性验证。对实验结果进行分析,得出相关结论,根据结论提出相关猜想,基于猜想去判断大点数图的优雅性,通过对大点数图进行标号,判断猜想是否成立。研究表明,对于图G（p,q）,当2≤p≤9,p≤q≤2p且q≠1（mod 4）时,所有图都是优雅图。当2≤p≤16时,所有的奇树都是优雅树;所有的偶数几乎都是优雅树。当2≤p≤16时,除图C5、C9和C13之外,所有的单圈图都是优雅图。对于（p,p+1）图,当4≤p≤16且p+1=1（mod 4）时,双圈图C（m,n）是非优雅图。对上述图形的奇优雅性进行一一验证,实验表明,当2 16时,所有的树都是奇优雅树。当2 9时,除几个图之外,所有只含有偶圈的图都是奇优雅图。QR码具有信息容量大、可靠性高、成本低、易于读取等特点,被广泛应用到社会各个领域。本文将QR码应用到产品的防伪方面,根据图的优雅标号算法生成图的优雅矩阵,结合产品的相关信息制作成“电子身份码”,添加到QR码中,从而可以根据客户的查询信息反馈商品的真伪性,维护客户的切身利益。

论文目录

• 摘要
• Abstract
• 1 绪论
•   1.1 引言
•   1.2 研究背景、目的及意义
•   1.3 本文的主要工作
•   1.4 本文的组织结构
• 2 图的相关理论
•   2.1 引言
•   2.2 图的基本概念
•   2.3 回溯与剪枝技术
•   2.4 本章小结
• 3 随机图的优雅标号算法
•   3.1 引言
•   3.2 算法设计
•     3.2.1 解决思路
•     3.2.2 算法的流程图
•     3.2.3 优雅图判定算法
•   3.3 算法示例
•   3.4 算法分析
•   3.5 算法结果与猜想
•     3.5.1 9 个点内的所有图
•     3.5.2 16 个点内的树图
•     3.5.3 16 个点内的单圈图
•     3.5.4 16 个点内的双圈图
•   3.6 本章小结
• 4 随机图的奇偶图判断算法和奇优雅算法
•   4.1 引言
•   4.2 奇偶图判断算法
•     4.2.1 解决思路
•     4.2.2 算法的流程图
•     4.2.3 奇偶图判定算法
•     4.2.4 算法示例
•   4.3 奇优雅判断算法
•     4.3.1 解决思路
•     4.3.2 算法的流程图
•     4.3.3 奇优雅图判断算法
•     4.3.4 算法示例
•     4.3.5 算法分析
•   4.4 算法结果与猜想
•     4.4.1 9 个点内的所有图
•     4.4.2 16 个点内的所有树图
•   4.5 本章小结
• 5 图标号在QR码防伪中的应用研究
•   5.1 引言
•   5.2 QR码的相关介绍
•     5.2.1 QR码的特点
•     5.2.2 QR码的基本结构
•     5.2.3 QR码的编码过程
•   5.3 .QR码的防伪应用
•     5.3.1 QR防伪技术的背景
•     5.3.2 QR防伪技术的设计
•   5.4 QR码的防伪性能分析
•   5.5 本章小结
• 结论
• 致谢
• 参考文献
• 攻读学位期间的研究成果

文章来源

类型: 硕士论文

作者: 赵科

导师: 李敬文,徐向前

关键词: 优雅标号,优雅图,奇优雅标号,二维码,防伪功能

来源: 兰州交通大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 兰州交通大学

分类号: O157.5

DOI: 10.27205/d.cnki.gltec.2019.000215

总页数: 78

文件大小: 6956K

下载量: 25