一些特殊图类的弱罗马控制数的研究

一些特殊图类的弱罗马控制数的研究为了研究格子图的弱罗马控制数，我们从格子图、格子图等开始做起，使研究一步步加深。罗马控制函数（简称EDF）是由Ian stewart所发表的名为“Defend the Roman Empirel！”的文章中提出的。之后M.A.Henning提出了新的策略来防御罗马帝国，即弱罗马函数(WRDF)，这种策略既节省军队的费用又可以防御整个帝国。格子图和弱罗马控制的结合对研究弱罗马控制开创了新的空间，在本文中，给出了格子图的弱罗马控制数的上下界和详细的证明过程。11第一章 引言1.1 罗马控制数的历史来源可以用一个有关罗马帝国军事战略的历史轶事定义和解释罗马控制数，在公元三世纪罗马帝国占据了欧洲的大部分地区、北非和近东，为了保卫它的边境和帝国本身，使用了前沿防御战略，它的五十个罗马军团可以保护即使最边远的地区。1 在公元四世纪，当罗马帝国失去了它原有的力量，军团的数量大幅下降，君士坦丁大帝发明了深度防御策略，当地的部队用来阻止入侵和叛乱，另有四个机动集团军被用来做最后的阻止力量。在这项新策略中，一个地区如果有至少一个机动集团军驻扎，那么它就被认为是安全的。另一方面，如果存在一个与地区A相邻的地区B（即可以一个步骤就从B到A，中间不跨过第三个地区），B配置有至少两个机动集团军，则地区A被认为是可使安全的。君士坦丁大帝时代的罗马地区之间的联系如图1.1，每个地区以一个圆表示，用一条直线表示两个地区之间一个步骤可到达。在上个世纪，罗马帝国的每个地区都有八个机动集团军驻扎，然而现在康士坦丁面临的挑战是分配仅有的四个机动集团军来保卫帝国的所有地区。当时，君士坦丁选择在帝国的两个首都罗马（Rome）地区和君士坦丁堡（Constantinople）地区各驻扎两个机动军团。这样除了不列颠地区（Britain）之外，这一部署使所有地区为安全的或者是可使安全的，这样看来不列颠（Britain）地区是罗马帝国第一个失去的地区并非是一个巧合了。图1.1 君士坦丁大帝时代的罗马用现代的方式来分析，还有其他的解决方案可以确保帝国的所有地区是安全的或者可使安全的： 在不列颠（Britain）地区部署一个机动集团军，在罗马（Rome）地区部署两个机动集团军，在小亚细亚（Asia Minor）地区部署一个机动野战集团军。 在高卢（Gaul）地区部署两个机动集团军，在埃及（Egypt）地区部署两个机动集团军。这样部署有一个缺点是对于罗马帝国的两个首都，至少有一个是完全无防备的，这对于君士坦丁大帝是不会去考虑的解决方案。有两个例子使用相同的防御策略，一个是十九世纪大英帝国为了防御它广阔的地区，此时大英帝国拥有四个战斗舰队去防守六个海洋区域。另一个是冷战之后的美国，拥有四个武装力量去防守五个地区。21.2罗马控制数的引入罗马控制函数的定义来源于Ian stewart3发表的一篇论文“Defend the Roman Empirel！”。所研究的格子图中，每一个点代表罗马帝国的一个地区，如果一个地区有军团驻扎则认为其是安全的，否则被认为是不安全的。但如果可以从相邻的一个地区（点）派遣一个军团到达一个不安全地区（点），那么则认为不安全地区（）能够被安全防御，并且这样派遣之后原来的安全地区（）不能够变成不安全地区。因此，为了达到防御罗马帝国所有地区的目的，帝国的统治者采用一种派遣军团的方案，既：派遣一个军团去与之相邻的不安全地区之前，需要在该地区驻扎两个军团。这样每一种派遣方案对应一个罗马控制函数。E.J.Cockayne等在4中给出了一个图上的罗马控制函数（简称RDF）的定义：在上的函数称为图的一个罗马控制函数，若其满足：每一个的顶点至少连接一个顶点且 。把函数的权记为,并且我们定义，对于任意一个，有，则称函数为罗马控制函数（RDF）。记图的罗马控制函数的最小权为，称为罗马控制数，即 ，称一个权为的罗马控制函数为一个-函数。1.3弱罗马控制数的引入 使用罗马控制这种方法来防守罗马帝国所产生部队闲置的代价会很大，为了探究怎样节约统治者最基本的部队给养的花费，并且仍然可以防御罗马帝国的所有地区，M.A.Henning5提出了新的派遣方式：任一个不安全地区都要与一个安全的地区相邻，并且从一个安全地区派遣军团去不安全地区后，不会产生未防御地区，这样派遣前后都没有未防御地区，这种新策略仍然能够防御整个罗马帝国，即为弱罗马控制函数，并给出了弱罗马控制函数（简称为WRDF）的概念：设是一个图，是图G上的函数，对于函数和顶点，则称顶点u为未防御点，如果它不与任何一个带正权的顶点相邻。如果任意一个的顶点都和一个的顶点相邻，并且使新得到的函数没有未防御点，其中，对有，则称函数为弱罗马控制函数。设是一个图，设在的作用下取值分别为0,1,2的顶点集为。在函数与图的顶点集的划分之间存在一一对应的关系，记为。定义函数的权，图的一个弱罗马控制函数的最小权是弱罗马控制数，记其为，所以有。一个权为的弱罗马控制函数称为-函数。从罗马控制函数和弱罗马控制函数的定义中可以发现，弱罗马控制函数中的每一个在中的点都被中的点控制住；而在罗马控制函数中，每一个中的点都至少被中的一个点所控制，显然使用这种策略的代价更加的昂贵，因此研究图的弱罗马控制函数更具有现实意义。第二章 相关的已知结果在此给出有关弱罗马控制的一些已知结果。引理2.15:对任意的图，有引理2.25:对，且，有。引理2.35:对，且，有。引理2.46:对任意一个的格子图，有 引理2.57:对任意一个的格子图，有 引理2.69:对任意一个的格子图，且，有 引理2.75:图G的任何一个罗马控制函数同时也是一个弱罗马控制函数。引理2.88:对任意，有 第三章 主要结论与证明3.1 主要结果 定义9：对任意两个图G和H，规定为一个以为顶点集，以为边集的图，其中， 。对， 称为一个格子图。在本文中，我们有如下结果：命题3.1当n9时， 当n31时， 3.2 大致范围的确定下面是为证明命题3.1做的预备3.2.1 方法一 由引理2.2和引理2.3，已知和，要找出格子图的上界，可以把格子图看作由许多圈组成的，当n为偶数时，有个圈；当n为奇数时，有个圈，并且中间多一个顶点。将所有圈的弱罗马控制数相加，由此可以粗略得到一个上界，即具体证明过程如下： 且， 当n为偶数时，共有个圈，最小单元为一个的格子图，也可看作，圈中点数依次为，则 当n为奇数时，共有个圈，多出中间一个顶点，圈中点数依次为，则 所以可得 3.2.2 方法二 由引理2.3到引理2.6，已知的弱罗马控制数，现在分四种分类方式：1. 将的格子图看作由个的格子图，如有余下的则用或或的格子图填补所构成。2. 将的格子图看作由个的格子图，如有余下的则用或的格子图填补所构成。3. 将的格子图看作由个的格子图，如有余下的则用的格子图填补所构成。4. 将的格子图看作由n个构成。按照方式1时计算弱罗马控制数的上界： (n9) 按照方式2时计算弱罗马控制数的上界： （n9）按照方式3时计算弱罗马控制数的上界： n为偶数时 n为奇数时 按照方式4时计算弱罗马控制数的上界：从中我们可以知道当n9时，的上界可以控制在的范围左右，由此猜测证出。下面为其证明。3.3 上界的确定 定义：对任意两个图G和H，规定为一个以为顶点集，以为边集的图，其中， 。对，是一个的格子图。设，其中，。命题3.3.1 对任意的n3,有 .证明：设的定义如上，构造一个弱罗马函数，令，设，并且定义函数，则有。因此3.4 下界的确定 由引理2.1可知，而在引理2.8中了解到，当时，对于的格子图有，因此可知。下面为对下界的讨论按照方