论文部分内容阅读
图论是离散数学的一个重要分支,它在物理、化学、天文、地理、生物学,尤其是计算机科学中有非常广泛的应用.
本文主要研究图的边的控制数问题,图的控制问题是由Claude Berge于1958年和Oystein Ore于1962年提出并进行研究的,Ore真正使用了控制该术词,1977年维多利亚大学的Ernie Cockayne和克莱姆森大学的Stephen Hedetniemio合作的一篇文章发表,从此,控制成为许多专家感兴趣的一个研究专题.近二十年来,随着信息化和数字化技术的不断进步,许多实际问题的数学模型促使人们对离散型结构上的数字化技术更加关注,也使得图的控制理论成为图论新的研究分支.
加拿大著名图论专家Cockayne等先后引入了图的许多不同类型的控制概念及其变化形式.1998年,美国图论学者Haynes等出版了专著《Domination in Graphs》和《Fundamentals of Domination in Graphs》较为系统地综述了一些主要研究成果.然而值得注意的是,几乎所有的概念和结果都是针对图的点控制而言,很少涉及图的边控制问题.为了进一步丰富和完善图的控制理论内容,我国学者徐保根教授于2006年将图的点控制概念扩充到研究图的边控,并取得许多研究成果,如符号边控制、符号星控制、符号局部控制等.本文讨论的是边控制数问题.主要讨论的是正则图的边控制数的上下界以及peterson图的边控制数.
本文重点研究了部分图的符号边控制数问题.对于正则图,本文利用正则图的特性通过严格的数学证明,确定了一般正则图边控制数的上、下界,并且给出了达到下界的必要条件,同时还构造出了达到下界的特殊图.对于peterson图,本文利用算法设计与分析中的回溯与分支限界的理论设计了peterson图的符号边控制数的算法,将计算机构造性证明与数学证明相结合,确定了广义petersen图p(n,1)和p(n,2)符号边控制数.