文献综述
一个图的一个控制集是的一个顶点子集,使得不在中的每个顶点都与中的某个顶点相邻.图的具有最少顶点数的控制集所含的顶点数称为的控制数,记为.一个无孤立点的图的一个全控制集是的一个顶点子集,使得的每一个顶点都与中的某个顶点相邻.图的具有最少顶点数的全控制集所含的顶点数称为的全控制数,记为.
图的控制集以及全控制集是图论中的重要的概念,与图的其他概念像独立数、完美匹配等有着密切的联系.据考证,对图的控制数的研究源于国际象棋.在国际象棋的棋盘上,最少放置几个皇后就可以使得棋盘上所有的位置都能被一个皇后攻击或占据,随着人们开始研究探索,在十九世纪五十年代发现5个皇后就能够做到.这可以看作图的控制数的最早雏形,而像这样的5个皇后问题就是找一个5个皇后的控制集.1958年, Berge的图论专著中首次出现“控制数”这一概念.1962年,Ore的图论著作中正式定义和使用控制术语“domination set”和“domination number”.1977年,Cockyane和Hedetniemi在一篇短的综述报告中开始用符号表示图的控制数且沿用至今.1998年,Haynes等人出版了两本专著,系统的介绍了一些图的控制集理论,同时给出了许多实际应用的例子.自此，图的控制集理论得到了前所未有的发展,在发展的过程中提出了更多与控制相关的概念,并得到广泛的研究,其中对于全控制的研究是最为基础的一类.
图的控制集问题在无线通讯台建设、社区网络选址、土地勘测等诸多社会生活、工程技术中具有广泛的应用.例如,在一个工厂中,将每个职工看成一个顶点,两个顶点连一条边当且仅当对应的职工存在管理与被管理关系.这样就得到一个图,而全体管理者对应的顶点做成一个集合就是这个图的一个控制集.
一个曲面包括可定向曲面和不可定向曲面.一个可定向曲面可由一个球面添加个环柄得到,而一个不可定向曲面可由一个球面添加个麦比乌斯带得到,其中分别称为和的亏格.分别称为球面和环面,分别称为射影平面和克莱因瓶.
1996年,G.MacGillivray 和K.Seyffarth[8]研究了平面图的控制集问题.文章通过对图的直径进行进一步的限制,证明了直径为2和3的平面图形具有有界控制数,还给出了直径为4的平面图的例子,以及直径为2的非平面图,具有任意大的控制数.2009年,M.D.Plummer 和Xiaoya Zha[10]研究了嵌入在环面和克莱因瓶上的图的控制数问题.文章证明了在环面和克莱因瓶中三个连通图的嵌入,分别包含了一个生成的圆柱体和一个具有一定性质的生成环子图.然后,他们将这些结果应用于图的控制数的研究中,结果表明,在环面和克莱因瓶的三角化过程中,结果为n/3.2010年,E.L.C.King 和 M.J.Pelsmajer研究了平面三角剖分图的控制集问题.他们发现,对于n足够大,任意顶点为n的三角剖分的控制数最多为n/4.
因此,在本项目中,我将研究嵌入在小亏格曲面上的网格图的全控制集问题.
参考参考文献:
[1]Alvarado I D, Dantas S, Rautenbach D.Perfectly relating thedomination, total domination, andpaired domination numbers of a graph[J],Discrete Math. 2015,338:1424-1431.
以上是毕业论文文献综述，课题毕业论文、任务书、外文翻译、程序设计、图纸设计等资料可联系客服协助查找。
