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