图的优美标号算法及在PDF417码防伪中的应用研究

论文摘要

图论是组合数学的一个重要分支,也是计算机领域中的基础科学。图论中的所有研究是以图作为研究对象,对图进行操作,例如:图染色、图标号等。如今,机器学习、神经网络中的很多基础算法便是基于图论而提出,计算机的出现也很大程度推动了图论基础科学的发展。图标号作为图论中的一个重要研究方向,具有很好的理论背景以及很广泛的应用价值。现实世界中的许多组合优化问题可以抽象为图标号问题,对图标号进行理论分析,从而解决相关问题。对图进行标号本质上是寻找一个映射关系,例如图的优美标号,对于一个图,且|（1（）|=,|（）|=,如果存在一个单射1）:（1（）→{0,1,2,…,},使得边标号集合{1）（）|∈（）}={1,2,…,},且每条边的标号满足1)（）=|1)（）-1)（）|,则称为优美图,1)是图G的一个优美标号。图的优美标号是最早提出的一类标号,优美标号源于Rosa提出的“优美树猜想”,该猜想指出:所有的树都是优美树。由于图结构的不确定性,目前该猜想仍未被证明,但优美树猜想的提出为图标号的发展奠定了基础。许多特殊的图现已被证明是优美图,并得到了不错的结论,但是这种证明过程是传统的组合构造方法,是对结构确定、有规律的图进行的证明,对于随机的、一般的图,目前并没有好的方法来证明图的优美性,该问题是NP困难问题。传统组合构造法具有局限性,针对的是特殊图,且优美标号规律一般很难寻找,而计算机算法可以解决一般图的优美性。利用计算机算法来解决图的优美标号问题,这类文献较少,并没有一个通用的算法。针对上述问题,本文提出一般图的优美标号算法,以及图的奇优美标号算法,并提出将图的标号与PDF417码相结合的思想,对产品进行防伪溯源,主要研究工作如下:（1）介绍图论中的基本概念、图标号研究现状以及图标号的部分现有结论;（2）介绍了有限点内所有非同构图的生成算法,以及g6文件编码原理;（3）设计并提出了两种图的优美标号算法,分别是“基于优美空间搜索优美图算法”和“基于邻接矩阵判定优美图算法”,该算法可以解决有限点内任意图的优美性,利用该算法,分别对9个点内的所有图、18个点内的单圈图和17个点内的双圈图进行了优美性验证,并得到了相关统计数据及结论。（4）图的奇优美标号是将图的边标号集合限定在奇数范围。针对图的奇优美标号,本文提出了图的奇优美标号算法,利用该算法,对9个点内的所有图进行了奇优美性验证,并得到相关结论及定理。对数据分析得出,在该范围内,只要一个图中不包含奇圈,则该图是奇优美图。因此,文中给出了一种判断一个图是否含有奇圈的方法。（5）结合图的标号算法与PDF417码,应用于产品的防伪溯源。并且介绍了PDF417码的编码原理,以及利用优美标号算法对产品进行防伪的相关思想。

论文目录

• 摘要
• Abstract
• 1 绪论
•   1.1 课题背景及意义
•   1.2 国内外研究现状
•   1.3 主要研究内容
•   1.4 论文组织结构
• 2 图标号理论概述
•   2.1 图的基础理论
•   2.2 图标号相关概念及定义
•   2.3 标号研究现有结论
•   2.4 本章小结
• 3 图的生成算法
•   3.1 g6文件编码原理
•   3.2 算法实验结果
•   3.3 本章小结
• 4 一般图的优美标号算法
•   4.1 基于优美空间搜索优美图算法
•     4.1.1 算法描述
•     4.1.2 预判断函数
•     4.1.3 图的连通性判断方法
•     4.1.4 算法测试
•     4.1.5 算法结果与分析
•   4.2 邻接谱求解算法
•     4.2.1 算法描述
•     4.2.2 算法示例
•   4.3 基于邻接矩阵判定优美图算法
•     4.3.1 算法描述
•     4.3.2 预判断函数
•     4.3.3 图的自同构变换
•     4.3.4 算法测试
•     4.3.5 算法结果与分析
•     4.3.6 实验结果
•   4.4 算法比较
•   4.5 本章小结
• 5 一般图的奇优美标号算法
•   5.1 算法描述
•   5.2 判断一个图中是否含有奇圈
•   5.3 算法结果与分析
•   5.4 本章小结
• 6 图的优美标号理论相关应用
•   6.1 利用PDF417 码防伪溯源
•     6.1.1 概述
•     6.1.2 PDF417 二维码结构
•     6.1.3 PDF417 码结合优美标号算法
•   6.2 本章小结
• 结论
• 致谢
• 参考文献
• 附录 A 各程序运行截图及说明
• 攻读学位期间的研究成果

文章来源

类型: 硕士论文

作者: 魏众德

导师: 李敬文

关键词: 图的优美标号,优美图,奇优美图,优美空间,码防伪

来源: 兰州交通大学

年度: 2019

分类: 基础科学

专业: 数学

单位: 兰州交通大学

分类号: O157.5

DOI: 10.27205/d.cnki.gltec.2019.000510

总页数: 81

文件大小: 4122K

下载量: 24