论文部分内容阅读
图论是应用数学的一个分支,它以图为研究对象,图论中的图是由若干给定的点及连接两点的线所构成的图形,这种图形通常用来描述某些事物之间的某种特定关系,用点代表事物,用连接两点的线表示相应两个事物间具有这种关系.图论是欧拉在1763年解决柯尼斯堡七桥问题的过程中创立的,而在在过去的的三十年里,图的“控制”的研究是图论中发展最快的领域.这一研究领域出现之所以这么迅速,主要因素有以下三点:(一)它在现实世界和诸如“覆盖”“位置确定”类数学问题中有着广泛而深刻的应用.例如目前编码理论中正在研究的码长为n覆盖半径为r的二进制码的最小数K(n,r)正是图的控制集理论中超立方图的r-距离控制数,显然,图论中的距离控制数更具有一般意义.现在,人们已发现图的控制集理论可广泛应用于编码理论,计算机科学,通信网络,监视系统和社会网络等理论与实践中.(二)控制参数定义类型的多样性.根据实际背景的不同,现已定义的控制参数有几十种之多,随着研究的深入和应用的激发,新的参数如雨后春笋,不断涌现.(三)图的控制参数确定问题的NP-完全性与其它组合优化中NP-完全问题紧密而自然的关系.确定一般图的控制参数(控制数,全控制数和成对控制数)的问题一般都是NP困难的(NP-hard).因此,确定一些较特殊图的控制参数也具有较为重要的意义.本文首先介绍了图,笛卡尔乘积,全控制,控制数,成对控制及成对控制数的基本概念,还有图的一些表示符号以及有关全控制数,成对控制的结论,并借鉴了图与图的笛卡尔乘积,图的控制和全控制等基本概念,研究路与圈的全控制,给出并证明对应的全控制和成对控制的数值.主要内容包括:(1)结合路与路,圈与圈的笛卡尔乘积的全控制数得出了路与圈及圈与路的笛卡尔乘积的全控制数的范围.(2)确定路与圈和圈与路的笛卡尔乘积的全控制数及成对控制数.