图的反魔幻性猜想的研究

发布时间：2020-03-30 10:49

【摘要】：图论作为离散数学的一个重要分支,综合了群论、矩阵论、概率论、拓扑学等其他学科的知识,在化学、物理、天文、地理、生物、计算机科学等领域有着广泛的应用.图的反魔幻标号问题起源于1990年Hartsfield和Ringel在文献[1]中提出的两个猜想:1、所有连通图除K2外都是反魔幻的;2、所有树除K2外都是反魔幻的.图G =(V,E)的边标号是图的边集到整数集的一个双射,即φ:E→{1,2,…,|E|}.对G的任意顶点u,其标号和定义为fφ(u)=∑e∈E(u)φ(e),这里E(u)是指与顶点u关联的所有边的集合.一个图被称为是反魔幻的,如果存在图G的一个标号φ,使得V(G)中任意两个不同的顶点u,v有不同的标号和,即fφ(u)≠fφ(v).以上两个猜想一经提出,立即引起了国内外众多学者的重视并得到了许多结果.许多特殊的图已经被证实其反魔幻性,例如,简单的图类有路、圈、轮图、星图、双星图、扇图、联图、完全图、三正则图等,复杂的图类有稠密图、正则图、奇正则图、正则二部图、树、网格图和棱柱图、笛卡尔乘积图、平面图、推广的锥形图、有向图等.这一猜想目前还没有得到完全解决,仍然具有高度的开放性.图的反魔幻标号在计算机网络理论中得到了很好的应用,例如,网络需求负载不平衡问题:当我们用不同容量的路由器建立网络时,就可以考虑用边的反魔幻标号表示路由器之间的宽带容量.本文主要研究两种图——字典乘积图、融合图的反魔幻标号问题.利用矩阵对图的完全二部子图进行标号,并采用调换的方法解决标号和冲突(即两个不同的顶点有相同的标号和)的问题,最后得出两条路的字典乘积图、两个完全图的融合图是反魔幻图的结论.本文所得到的结果是对图的反魔幻性研究领域的一个补充,同时改进、推广和统一了许多学者的最新研究成果.全文一共分为四个部分:第一部分是绪论.这里主要介绍了图论的历史、选题的背景、研究现状以及图论中的一些基本概念.第二部分研究了两条路的字典乘积图的反魔幻性.首先介绍了字典乘积图的概念以及两条路的字典乘积图的标号技巧,其次展示了在标号过程中得到的六个声明,然后提出解决顶点标号和冲突的方法——调换,最后分类证明了两条路的字典乘积图是反魔幻的.第三部分研究了两个完全图的融合图的反魔幻性.首先是介绍融合图的概念,然后用构造出来的主对角线为0的特殊分块矩阵对其边进行标号,最后证明两个完全图的融合图是反魔幻的.第四部分是总结与展望,总结本文得出的两个结论——两条路的字典乘积图、两个完全图的融合图是反魔幻的,同时展望了在以后的工作中将要研究的问题——探究Spider图、Halin图、双正则二部图、双正则图的反魔幻性以及图的反魔幻性在实际中的应用.
【学位授予单位】：天津工业大学
【学位级别】：硕士
【学位授予年份】：2018
【分类号】：O157.5

【相似文献】