论文部分内容阅读
图论是计算机科学基础的一个重要分支之一,1736年瑞典数学家欧拉的一篇关于“哥尼斯堡七桥”问题的论文拉开了图论研究的序幕。自图论成为一门单独的学科以来,经过了多年的发展,已经形成了完备的研究体系,具备了很高的理论价值和应用价值。图论最初只是应用于解决如迷宫问题、博弈问题等一些游戏中遇到的问题,19世纪末期图论已经被应用于网络方程组和有机分子结构等研究领域,20世纪以后伴随着计算机的出现,图论的应用已经深入到很多领域的不同层面。譬如我们可以以图作为模型解决诸如通信网络、生产管理、交通运输、任务分派等方面的实际问题。如今图论有了更为广泛的发展和应用,图论本身及其在信息论、物理学、化学、网络理论、社会科学、管理科学等诸多领域都已经受到了人们的广泛重视。图是图论的主要研究对象,给定一个图我们要判定这个图所具有的性质,如判定一个图是否存在哈密顿圈,是否为平面图或者是不是欧拉图等。传统的研究方法可分为直接证明的研究方法(如直接判断一个图是不是哈密顿图)和间接证明的研究方法(如由子图的性质推导母图的性质)。本文在图的传统的研究方法基础之上,结合图的性质、运算方法等提出了图的运算不变性的运算方法,重点讨论了在笛卡尔积运算下和张量积运算下图的若干不变性,并得出了图的非平面性、哈密顿性在图的笛卡尔积运算下具有不变性;图的平面性、非哈密顿性、欧拉性在图的笛卡尔积下不具有不变性;图的哈密顿性、正则性在图的二分倍覆盖下具有不变性;图的非平面性在图的张量积运算下具有不变性等一些重要结论,利用这些结论证明了超级立方体中存在哈密顿圈和笛沙格图的非平面性,并给出了超级立方体的哈密顿圈的软件生成算法。本文的创新之处:对图的研究方法采取了不同于传统的研究,另辟蹊径在前人研究的基础之上提出了图的运算不变性的运算方法,把一个复杂图分解为若干个简单图的运算,利用运算不变性对子图的性质(如平面性、非平面性、欧拉性、哈密顿性等)进行分析,逆向推导复杂母图的性质。这种研究方法简化了图的研究难度,提高了图的研究效率,为我们对图的研究提供了一个新的思路。