（运筹学与控制论专业论文）图的弱罗马控制.pdf

煎壹盔堂塑主堂垡迨塞 l 摘要 基于i a ns t e w a r t 1 l 】发表的一篇论文( d e f e n dt h er o m a ne m p i r e ! ，s c i e n t i f i ca m e r - i c a n ，d e c 1 9 9 9 ，p p 1 3 6 - 1 3 8 ) 的意图，m a h e r m i n g 和s t h e d e t n i e m i 【l 】1 提出了防御罗 马帝国的新策珞使最高统治者既节约了给养军团的基本花费又能防御罗马帝国用 图论的术语，设g = ( v ，e ) 是个图，：y 一 o ，1 ，2 ，是一个定义在图g 的顶点 集y 上的函数对，来说一个，( “) = 0 的顶点u 被称为未防御点，如果它不与任 何带有正权的顶点相邻函数，被称为弱罗马控制丞数( 简称w a d f ) ，如果对每一 个，( “) = 0 的顶点u ，都与一个( v ) 0 的顶点口相邻，并且函数，：y 一 o ，1 ，2 h 使得，7 ( “) = 1 ，7 ( 。) = ，( 口) 一1 且，7 ) = ( w ) ，v 伽v 一 _ ) ，没有未防御点 函数，的权记为叫( ，) = * y ，扣) 图g 的弱罗马控制函数的最小权称为弱罗马控 制数，记为* ( g ) ，在本文中，研究了图的不同控制数的一些理论性质，并且刻画 了树t 满足竹口) = 7 ( r ) 的特征和图g 满足镛( g ) = 1 ( g ) + 1 的特征，以及满足 * ( g ) = 2 7 ( g ) 的图g 的一些性质 关键词；控制数，树，弱罗马控制数 河宣大学硕士学位论文 a b s t r a c t m o t i v a t e db ya l la r t l e l eb yi a ns t e w a r t 【1 1 j ( d e f e n dt h er o m a ne m p i r e ! ，s c i e l l t i f i c a m e r i c a n ，d e e 1 9 9 9 ，p p 1 3 6 - 1 3 8 ) ，m a i - i e n n i n ga n ds t t t e d e t n i e m i1 1 】1e x p l o r ean e w s t r a t e g yo fd e f e n d i n gt h er o m a ne m p i r et h a th a st h ep o t e n t i a lo fs a v i n gt h ee m p e r o r c o n s t a n t i n et h eg r e a ts u b s t a n t i a lc o s t so fm a i n t a i n i n gl e g i o n s ，w h i l es t i l ld e f e n d i n gt h e r o m a ne m p i r e i ng r a p ht h e o r e t i ct e r m i n o l o g y ，l e tg = ( k e ) b eag r a p ha n dl e t ， b ef u n c t i o n ，：vh 0 ，1 ，2 ) av e r t e x w i t h ，0 ) = 0i ss a i dt ob eu n d e f e n d e dw i t h r e s p e c tt o ，i fi t | 埠n o ta d j a c e n tt oav e r t e xw i t hp o s i t i v ew e i g h t t h ef u n c t i o n ，i sa w e a kr o m a nd o m i n a t i n gf u n c t i o n ( w t l i ? f ) i fe a c hv e r t e x “w i t h ，( ) = 0i sa d j a c e n tt o a v e r t e x 寸w i t h ，p ) 08 u c h t h a t t h e f u n c t i o n ：v h ( o ，1 ，2 ，d e f i n e db y ，7 ( = i ， ，( 口) = f ( v ) 一1a n d ，( ) = ( w ) i f v t ) ，h a sn ou n d e f e n d e dv e r t e x t h e w e i g h to f ，i 8 ( ，) = * v ，( u ) t h ew e a kr o m a nd o m i n a t i o nn u m b e r ，d e n o t e d * ( g ) ， i st h em i n i m u m w e i g h to faw r d f i ng i nt h i sp a p e r is t u d yt h eg r a p ht h e o r e t i cp r o p - e r t i e so ft h l sv a r i a n to ft h ed o m i n a t i o nn u m b e ro fag r a p h a n dic h a r a c t e r i z et r e e stf o r w h i c h 竹( q = ，y ( ? ) a n dg r a p h s g 矗”w h i c h 竹( g ) = 一r ( q + 1 ，a n d ig i v e t h eg r a p h g s o m ep r o p e r t i e sw i t h 竹( g ) = 2 1 ( g ) k e y w o r d s ：d o m i n a t i o nn u m b e r ，t r e e s ，w e a kr o m a nd o m i n a t i o nn u m b e r 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学住串请。本人郑重声明：所呈交的学柱论又是 表人在导师的指导下独立完成的，对所研究的课题有新的见解。据我所知，除 文中特刷加科说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果也不包括其他人为获得任何教育、科研机构的学位或证书而 使用过酌材料。与我一同工作酌同事对本研究所儆酌任何贡献均已在论卫中作 了明确的说明并表示了谢毒。 学位中请八( 学位论作者) 鍪名： 煮兹刽 2 0 叼年岁月幻。 关于学位论文著作权使甩授权书 本人经河南太喾审核批准授予硕士学位。作为学位论夏酌作者本人完全 了解并同意河南大学有关保留、使用学位论文的要求，即河南大学有权南国家 图书馆、科研信息机构、数据收集机构和本校图书馆等提供学位论文( 纸质文 本和屯子咒本) 雌供公众检索、查阅。本人授权河南大学出于宣扬、展览学校 学术点展和进行学拳交流等目的，可以采取帮即、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 纸质文本和电子立本) 。 ( 涉度保密内容的学位论文在解密后适用本授权书) 擘位获得者( 学住论z 作者) 器名 壅之垒j 。o 0 7 年营月弘。 学住论文指导教师签名宝窒墅 翌童盔兰夔圭堂垡堡塞 l 第一章引言 e j c o c k a y n e 等在 3 】中给出了在一个图g = e ) 上的罗马控制函数( 简 称r d f ) 的定义：定义在矿上的一个函数f ：y 一 o ，1 ，2 ) 称为图g = ( v , e ) 的一个罗马控制函数如果它满足：每一个使f ( u ) = 0 的顶点u 至少连接一个顶点 _ 使，( 口) = 2 实值函数f ：v r 的权记为( ，) = * y fc v ) ，并且我们定义 f ( s ) ；e 。s ，0 ) ，vs v ，因此”( ，) = ，( y ) 图g 的罗马控制函数的最小权称为罗 马控制数，记为1 r c a ) ，也即7 r ( a ) = r a i n w ( f ) f 是g 的一个r d f 一个权为他( g ) 的r d f 我们叫做个他( g 卜一函数图的罗马控制的一些理论性质在 3 ，4 ，6 ，1 0 j 中 已经被研究过 定义罗马控制函数的意图来源于i a ns t e w a r t 1 1 1 在美国科学杂志上发表的一 篇题为“防御罗马帝国! ”的文章在我们所研究的图中的每一顶点代表罗马帝国 的一个地区一个地区( 顶点”) 被认为是不安全的，如果没有军团驻扎在那里( 即 ，如) = o ) ，否则被认为是安全的( 即，( u ) e 1 ，2 ) ) 一个不安全的地区( 顶点 ) 能够 被安全防御如果能够从相邻的地区0 的一个邻点u ) 派个军团到达该地区但是 在公元四世纪最高统治者颁布法令：个军团不能从一个安全地区派遣到一个不安 全的地区如果派遣后使得该地区不安全因此，在派出其中一个军团到相邻地区之 前必须在该地区驻扎两个军团( ，( ”) = 2 ) 最高统治者利用这种方式能够防御罗马 帝国因为在个地区给养个军团是很昂贵的，所以统治者想用尽可能少的军团 防御罗马帝国一个权为他( g ) 的罗马控制函数对应着个最优分派军团驻扎的方 案 为探究节约统治者基本的给养军团的花费，同时仍然能够防御罗马帝国的潜 力，m a h e n n i n g 【1 】1 等提出了新的策略令g = ( v , e ) 是个图，是个函数 ，：v 一 o ，l ，2 ) 设，m ，坞分别代表在，作用下取值分别为0 , 1 ，2 的顶点集注 意到在函数，：y 一 o ，1 ，2 ) 和顶点。的划分( ，u ，) 之间存在一一对应关系 因此我们记，= ( v o ，h ，) 在，对应下个顶点 v o 是未被防御点，如果它不与或中的顶点相 邻m a n e n n i n g 1 】等提出了弱罗马控制函数( 简称w r d f ) 的概念：称函数， 2 塑堕盔堂塑主堂垡堡塞 是一个w r d f ，如果对于每一个顶点，都邻接一个顶点”n u ，使得函数 ，：v 一 o ，1 ，2 ) 没有未防御点，其中，7 ) = 1 ，铷) = ，( 口) 一1 并且，( ) = ，( t j ) ， v v 一 ，u 我们定义，的权”( ，) 为i 碓f + 2 f f ，图g 的一个w r d f 的最小权称为弱罗马 控制数，记为竹( g ) ，即竹( g ) = m i n w ( f ) l f 是图g 的一个w r d f ) , 一个权为* ( g ) 的w r d f 称为竹( g ) 一函数为了方便，对y 的每一顶点”，我们记f ( n v 1 ) = ， 给出w r d f 定义的意图是基于下面的考虑仍然采用先前的记号，我们定义 一个地区是未防御的，如果这个地区与与之相邻的地区都是不安全的( 即没有军团 驻扎在那里) 因为个未防御地区是易受攻击的，所以我们要求每一个不安全地 区必须与个安全地区相邻，并且使得从这个安全地区派遣军团到不安全地区不会 产生未防御地区因此每一个不安全地区能够被防御而不会产生未防御地区利用 这种方式最高统治者仍然能够防御罗马帝国而这一种分派军团的方案对应着个 w r d f 且军团数目的最小值对应着w r d f 的最小权因为这种方案既能节约统治 者给养军团的花费又能防御罗马帝国，所以弱罗马控制引起了统治者的高度重视 注意到在w r d f 中每一个在中的点都被h u 砼中的某一点所控制，而在 r d f 中的每一在k 中的点至少被中的一点所控制( 这个显得很昂贵) 再者，在 w r d f 中每一个在中的点都能够被防御而不会产生新的未防御点。因此，研究 图的弱罗马控制更具有现实意义 本文主要围绕图的弱罗马控制展开讨论，研究了图的不同控制数之间的一些理 论陛质在本文的前半部分，主要给出了弱罗马控制数的一些特殊值以及它的上下 界；在文章的后半部分，主要刻画了树t 满足竹( t ) = 7 ( t ) 的特征和图g 满足 * ( g ) = 7 ( 回+ 1 的特征，以及满足竹( g ) = 2 ，y ( g ) 的图g 的一些性质。 塑宣盔堂塑主堂焦堡塞 3 第二章记号 我们一般采用文献 8 1 中的图论术语和记号特别地，让g = ( v , e ) 是一个 顶点集为矿，边集为e 且阶数为n 的图，。是y 的任意个顶点，顶点”的度记为 d ( 顶点u 的开邻域记为( 。) = 。v l u v e 且闭邻域记为m = 。 u ( 。) 对个集合s v ，它的开邻域记为( 研= u 。e s n ( v ) - s 且它的闭邻域记为旧= s u n ( s ) 个顶点u 被称为”关于s 的私有邻点，或简单的说是”的个s 一肌，如 果 叫n s = u 顶点”的所有s 一的集合肼( 钆s = m n s - 口h 被称为 口关于s 的私有邻集我们定义 关于f 的外私有邻集为e 即( 口，s ) = m ( ”，s ) 一 w ) 因此集合e p a ( v ，s ) v s 集合s 被称为是不多余的如果m ( 口，回0 ，vu s 设g = f ) 是一个图，s v 我们说集合s 控制集合u ，记着s 卜u ，如 果u s 中的每一个顶点至少邻接f 中的一顶点如果s - v s 或者等价地， = y ，则s 被叫做g 的一个控制集圈g 的最小控制集的基数称为最小控制 数，记着7 ( g ) 一个基数为7 ( g ) 的控制集称为，y ( g ) 一集我们注意到每个最小 控制集是一个最大不多余集，但反之不一定成立例如，长度为5 的圈岛的每两 个相邻的顶点构成一个最大不多余集，但它却不是控制集图的控制集吲以及它 的变化形式目前已经有了很好的研究特别地，t w h a y n e s 8 ，9 】等给出了有关这一 主题的深入调查和研究 我们称图g 是罗马图，如果忱( g ) = 研( g ) 个顶点集合占被称为独立的，如果s 中的任意两个顶点均不相邻图g 的 独立控制集( 或者等价地，图g 的最大独立集) 的最小基数称为独立控制数，记着 t ( g ) 一个顶点集合s 被称为2 分离的，如果m n m = 死v u ，u s 图g 的 最大2 一分离集的基数称为2 一分离数，记着耽( g ) 个顶点集合s 被称为点覆盖集，如果v w e ，要么t s 要么 s 为了易于表达，我们常考虑带有根源的树对于( 有根源的) 树t 中任意一顶点弘 我们用c ( v ) 和d ( v ) 分别代表。的孩子和后代的集合，并且定义口m = d 扣) u ” 4 塑壹盔堂堡主堂焦丝塞 在顶点 处的极大子树是由d m 导出的子树，记着马一个度为1 的顶点称为树 t 的一个叶子( 又称为悬挂点) ，同时与叶子相邻的顶点称为树t 的支撑点，与至 少两片叶子相邻的顶点称为强支撑点在本文中。我们记所有支撑点集合为s ( ? ) ， 所有强支撑点的集合为8 s ( t ) ，所有盱子集合为工( t ) 对于任给的正整数t ，完全二部图甄t 称为星，并且称度为t ( t 2 ) 的顶点为中 心点，度为1 的顶点为外点，而情形p 2 中，我们称两个顶点都为中心点一个病 态的蜘蛛树是指一个星致 至多剖分它的t 一1 条边类似地，对于任给整数t22 ， 一个健康的蜘蛛树是指一个星确。剖分它的所有边在一个病态的蜘蛛树中，一个 度为t 的顶点将被称为头点，并且与头点的距离为2 的顶点称为脚点头点和脚点 是确定的除非当病态的蜘蛛树是两个或四个顶点的路对于p 2 ，我们将规定两个顼 点都为头点，而情形p 4 中，我们将规定两端的顶点都为脚点，并且两个中间点都 为头点， 在本文中，所考虑的图均为有限的非平凡简单图 翌塑盔竺塑望垡丝塞 5 第三章相关的已知结果 关于图的罗马控制和弱罗马控制已经有了很多的结论，本章主要是把与本文 有关的结论列出来，以便后面使麒其中第一节主要介绍有关图的罗马控制的一些 结果，第二节主要介绍有关图的弱罗马控制的一些结果 3 1 图的罗马控制 有关图的罗马控制的一些已知结果 命题3 1 1 3 对任何阶数为”的图g ，y ( g ) = 他( g ) 当且仅当g = ，不 命题3 2 1 3 设= ( ，珏) 是任何他一函数，则 ( a ) 由导出的子图c v 1 的最大度为l ； ( b m 和班之间没有边相连； ( c ) v o 中的每一个顶点至多与h 中的两个顶点相邻； ( d ) v 2 是g v o u 】的一个卜集； ( e ) 设h = g v o u 吲，则的每个顶点。至少有两个一肌( 即图日中 关于k 的私有邻点) ； ( f ) 如果”是g f b 】的孤立点并且仅有一个外日一册，记为”，则 ) n h = 毗 ( g ) 设k 为g 【吲中非孤立点数且，令d = ( v o h n ( v ) n 屹i 芝2 ) 且i c i = c 贝0n o 砌+ k + c 命题3 3 3 l 设= ( ，h ，v 2 ) 是无孤立点图g 的个佃一函数，使得n 1 最小 则； ( a ) 是独立集且k u 耽是个覆盖； ( b ) ； ( c ) k 中的每一个顶点至多邻接u 中的个顶点，即k 是一个2 一分离 6 塑宣盔堂堡主堂垡丝塞 集； ( d ) 设 g 吲恰有两个外一p n ，记为 1 ，坳v o ，则不存在点y l ，抛 使得， 1 ， ，地，y 2 ) 是一条路p 5 的顶点序列； e ) n e 3 n 7 ，并且这个界是紧的 命题3 4 3 】对任何阶数为n 且最大度为的图g ， 晶郇) 命题3 5 3 1 对任何阶数为n 的图g ， 榔胁等筹 注意1 ：此处可能由于作者的疏忽出现丁一些计算性错误，从而结论有误，在后 面应用时给予指出并修正 命题3 6 1 3 1 7 r ( p 。) ：垤( 岛) ：f 娑 命题3 7 1 3 设g = k m ，。，。是完全p 一部划分图，并且使得 i 7 1 m , 2 ；则： ( a ) 如果m l 3 ，则7 a ( a ) = 4 ； ( b ) 如果m l = 2 ，则7 r ( a ) = 3 ； ( c ) 如果m l = 1 ，则7 r ( g ) = 2 ； 命题3 s 1 3 如果g 是个阶数为n 且包含一个n 一1 度的顶点的图，则7 ( g ) = 1 且7 r ( g ) = 2 命题3 9 ( 3 】对任何2 n 格图g 2 m7 r ( g 2 ，。) = n + 1 命题3 1 0 1 3 】如果g 是阶数为n 的无孤立点的图，则7 r ( g ) = n 当且仅当n 是 偶数且g = ；鲍，其中；尬代表；个鲍的拷贝 命题3 1 1 1 3 如果g 是个阶数为n 的连通图，则7 a ( a ) = 7 ( g ) + 1 当且仅当 存在口v 使得d ( v ) = n 一7 ( g ) 命题3 1 2 f 3 j 如果t 是一个非平凡树，则他口) = 7 + 1 当且仅当t 是一个病 态的蜘蛛树 命题3 1 3 1 3 g 是一个阶数为n 的连通图，则他( g ) = 1 ( g ) + 2 当且仅当： ( a ) a 不含度为n 一7 ( g ) 的顶点； 塑查盔堂塑主堂垡堡塞 7 ( b ) g 有个度为n 一，y ( g ) 一1 的顶点或者有两个顶点v 和t c l 使得l n v l u n w l l = n 一7 ( g 1 + 2 命题3 1 4 1 3 】图g 是罗马图当且仅当它有一个垤一函数，= ( ，h ，) 使得 ”1 = i i = 0 命题3 1 5 1 3 】图g 是罗马图当且仅当7 ( g ) 7 ( g s ) + i i s i ，对每一个扯分离 集s v 命题3 1 6 1 4 如果g 是个阶数为n 的连通图，则 y r i ( g ) = ，y ( g ) + 当且仅当： ( a ) v1 j 一1 ，g 不含一个阶数为j 的子集s y 使得l 旧l 竹一( 7 ( g ) + i ) + 勿：j i 七一1 ( b ) a 含有一个子集岛v 使1 i s o i 且i n s o i = n n ( g ) + ) + 2 f 岛| 3 2 图的弱罗马控制 有关图的弱罗马控制的一些已知结果 命题3 1 7 1 1 1 图g 的任何个r d f 也是一个w r d f 命题3 1 8 1 1 】对任何图g ，7 ( g ) * ( g ) 他( g ) 2 7 ( g ， 命题3 1 9 1 v 口21 ，竹嘛) = 孥1 ；v n 24 ，* ( r ) ：* ( 岛) ；娑1 命题3 2 0 1 】对任何图g ，7 ( g ) ；竹( g ) 当且仅当存在一个，y ( g ) 一集s 使得： ( 1 ) v 口只弘0 ，s ) 导出一个团； ( 2 ) vt v ( g ) 一s 不是任何s 的私有邻点，存在一个点口s 使得 册( 口，印u ”，导出一个团 命题3 2 1 1 1 】如果图g 满足* ( g ) = 2 7 ( g ) ，则对每一个1 ( g ) 一集s 和每一个 口s ，外私有邻集q m ( ，s ) 包含两个不相邻的点 8 煎宣盔堂堡主堂焦堡塞 第四章主要结果与证明 这一章是得到的主要结果以及结论的证明其中第一节给出弱罗马控制数的 一些特殊值，第二节给出图的弱罗马控制的一些性质以及弱罗马控制数的上下界， 第三节刻画满足* ( = 7 ( 的树t 的特征，第四节刻画图g 满足* ( g ) = 7 ( g ) + 1 的特征，第五节给出了图g 满足* ( g 9 = 2 7 ( g ) 的些性质 4 1 弱罗马控制数的一些特殊值 e j c o c k a ：y n e 3 等给出了一些罗马控制数的特殊值，例如命题3 , 6 1 3 ，命题3 7 1 3 ： 命题3 8 f 3 j ，命题3 9 1 3 ，命题3 , z o 3 而m a h e n n i n g 1 等也已经给出了路和圈的弱 罗马控制数，例如命题3 1 9 1 1 作为补充我们再给出弱罗马控制数的一些特殊值 命题1 如果图g = 似聊的阶数为n 且包含一个度为n 一1 的顶点，则1 ( g ) = 1 并 且如果g = ，则竹( g ) = ，y ( g ) = 1 ；否则，* ( g ) = 他( g ) = 2 证明；设d 扣) = n 一1 ，则显然 。) 是一个控制集，即1 ( g ) = f ) i = 1 如果g = j h ，则v ”v ( g ) ，= 一t ”) ， 口h 毋) 是g 的一个弱罗马控制函 数( 因为任给”丘= ( v 一 u ) ， “) ，o ) 没有未防御点) 所以7 ( g ) * ( g ) ( ，) = i 口) f = 1 = 7 ( g ) ，即* ( g = 7 ( g ) = i 如果g j 矗，则必存在点z ，y 使得础e 且n 3 ，显然由命题3 1 8 l l 和命题3 s 3 1 有竹( g ) 协( g ) = 2 假如，= ( ，耽) 是一个竹( g ) 一函数且1 r ( g ) = 1 ，则设= o ，k = “) ， = v 一 u ) 显然u 。，g ( 否则y 或z 将为未防御点，矛盾) ，所以，( z ) = ，( ) = 0 ， 但是厶= ( v 一 。 ， z ，o ) 有一个未防御点们矛盾 故竹( g ) 2 因此* ( g ) = 仰( g ) = 2 口 塑宣盍堂塑主堂垡丝塞 9 命题2 设g = k m ，t ，1 2 。是完全n 一部划分图并且m ls 砌 h ( a ) 如果m 124 且n = 2 ，则竹( g ) = 4 ； ( b ) 如果”l24 且n 3 或m 1 = 3 ，则( g ) = 3 ； ( c ) 如果m l = 2 ，则* ( g ) = 2 ； ( d ) 如果“1 = 1 ，则 们) ： 1 ，如果g = i2 ，否则 证明；( a ) 如果m l 4 且n = 2 ，则g = k m ，m 为完全二部图记( x ，y ) 为i f , 的顶点划分，使得v = x u y ，x n y = 织i x l = m 1 ，l y l = m 2 下证，铷( g ) 4 假设* ( g ) 4 ，即* ( g ) 3 ，则存在一个弱罗马控制函数，= ( ，砼) 使得 ”( ，) = i h i + 2 i 班l = 3 因此有下面两种情形之一成立： 情形( 1 ) ：i i = 3 ，i k l = o ；情形( 2 ) ：i m i = 1 ，i l = 1 情形( 1 ) ：若h i = 3 ，i i - 0 。则分下面四种情况讨论：( 1 1 ) h = z 1 ，z 2 ，。3k ( 1 2 ) = 。l ，$ 2 ，舭，；( 1 3 ) m = ( z 1 ，饥，抛，；( 1 4 ) k = y l ，轨，拈) ，其中戤x ，讥 ei = 1 ，2 ，3 若= $ 1 ，却，知) ，1 k l = 0 由于i x l = m 1 4 ，则至少存在一顶点z 4 x 使 ，( 。4 ) = 0 显然钆点为未防御点，与假设矛盾 故( 1 1 ) 不成立同理，( 1 4 ) 也不成立 若u = 。1 ，现，姐) ，i i = 0 由于 x = m 1 4 ，则至少存在两个顶点$ 3 ，瓤 x 使，( z 3 ) = ，( z 4 ) = 0 即。3 ，z 4 而锄，瓤只与h u 中的点讥相邻，令 厶；m u i ， z 3 ) ，u 。3 ) 1 ) ，班) ，而z 4 为未防御点，与假设矛盾 故( 1 2 ) 不成立同理：( 1 3 ) 也不成立 因此( 1 ) i h l = 3 ，i 班i = 0 不成立 情形( 2 ) 若i h i = 1 ，i l = 1 ，则分下面四种情况讨论：( 2 1 ) = z l k = 。2 ) ； ( 2 2 ) h = z 1 ) ，= 1 ) ；( 2 3 ) = 讥， = 2 1 ) ；( 2 1 ) h = 讥 ，= 抛) ；其 中氟x ，玑y i = 1 ，2 1 0 河南大学硕士学盟论文 若h = z 1 ) ，k = z 2 k 由于陋l = m 1 4 ，则至少存在两个顶点$ 3 ，9 4 x 使f ( x 3 ) = ，( 。4 ) = 0 显然z 3 ，$ 4 为未防御点，与假设矛盾 故( 2 1 ) 不成立同理；( 2 4 ) 也不成立 若u = 讥 ，耽= 研) ，由于i x i = m 1 4 ，则至少存在三个顶点z 2 ，z 3 ，x 4 x 使，渤) = ，渤) = ，汹) = 0 而2 ，翔，2 7 4 只与u 砚= ( z i ，y 1 ) 中的点饥相邻 令厶= m u y 1 ) $ 2 ) ，u x 2 ) ( 1 ) ，) ，而为未防御点，与假设矛盾 故( 2 3 ) 不成立同理：( 2 , 2 ) 也不成立 综合情形( 1 ) ( 2 ) 可知* ( g ) 芝4 设z 1 五口1 y ，则显然，= ( v 一 l ，1 ) ，o ， 2 l ，y 1 ) ) 是图g 的一个r d f 且 权f ( v ) = ( ，) = 2 i 。1 ，y 1 ) i = 4 又由命题3 1 7 1 】可知，也是g 的个w r d f ，故 ，是图g 的一个竹( g ) 函数且* ( g ) = 4 ( b ) 设( 溉，弱，) 是g 的顶点划分，使得v = x 1 u 恐u u ，i 蜀i = 讹，x i n = 儿其中i j ，i ，j = 1 ，2 ，m 着m 1 = 3 ，则竹( g ) 23 假设* ( g ) 3 ，即竹( g ) 2 ，则存在一个弱罗马控制函数，= m ，k ，u ) 使得 ”( ，) = i h l + 2 f f = 2 因此有下面两种情形之一成立： 情形( 1 ) ：1 1 = 2 ，1 1 = o ；情形( 2 ) ：l 1 = 0 ，1 y 2 1 = 1 ， 情形( 1 ) ：若f k l = 2 ， 班f = 0 ，贝4 分下面两种情况讨论；( i 1 ) k = 甄【，锄 ，其中 。n ，t 2 蜀，忙1 ，2 ，仃( 1 2 ) = z n ，x j l ) ，其中茹 l 墨，即1 玛，t j ，i ，j = 1 ，2 ，n 若( 1 1 ) 成立，由于阢l = 讹m 1 = 3 ，i = 1 ，2 ，n 则至少存在一顶点 z 3 置使，( 。诌) = 0 显然z i 3 为未防御点，与假设矛盾 若( 1 2 ) 成立，由于阢l = 佻m 1 = 3 ，i = 1 ，2 ，n 则至少存在两个顶点 $ 口，z 置使，( 。拯) = y ( = i 3 ) = 0 而z 拯，$ 侣只与u = ( $ m 巧1 ) 中的点l 相邻令厶= ( 叭巧1 ) 。但 ，u 1 1 ：i 2 ) l ，) ，而为未防御点，与假设 矛盾 情形( 2 ) ：若i h i = 0 ，i l = 1 ，则设他= 。；1 ) ，其中。n 噩，i = 1 ，2 ，n 由于陇f = m f 铆= 3 ，i = 1 ，2 ，n 则至少存在两个顶点。谊，z i 3 咒使 塑宣盔堂塑主堂丝堡塞 1 1 ，扛程) = ， 得) = 0 显然锄，翰为未防御点，与假设矛盾 综合情形( 1 ) ( 2 ) 可知* ( g ) 3 又，= ( v 一，0 ) ( 其中= z l l ，z 1 2 ，z 1 3 ) 是g 的一个w r d f 且( ，) = 陬l = 3 ( 事实上，v 。诣v u ， = 2 ，n ，1 k ，f ( x 诹) = 0 且讯与z t l 相 邻，令厶= 一h $ 珏) z 1 1 ) ，m u x i k ) z n ) ，口) ，没有未i 劳御点) 故，是一个竹( g ) 一函数且* ( g ) = ( ，) = i n i = 3 若m l 4 且n 3 ，则竹( g ) 3 假设* ( g ) ( ，) ，矛盾我们 有f ( z i o i ) = ，( 一1 ) = o 如果，( “) = l ，黜有盎”，x 和牵( 丘”。) 毋( ，) ，矛 盾我们有，扛o + 1 ) = ，( + 1 ) = 0 ( 3 1 ) 当如；2 或者，( 一2 ) = ，( 一2 ) = 0 时，我们必须从。幻( ) 调动个军 团来保卫：r o - 1 ( 一i ) ，而且不能使2 o + 1 ( + 1 ) 成为未防御点因而我们有，( + 2 ) = ，( + 2 ) = 1 这样一来，我们定义 1 x 使得 1 4 塑堕盍堂塑主堂焦迨塞 h i ( ) = 1 ，= 矾。一1 ，z i o + 3 0 ， = y i o ，x i o + 2 ； ，0 ) ， 其它， 则曲( h 1 ( ，) ，矛盾 ( 3 2 ) 因此我们有i o 3 和，( 2 如一2 ) 十，( 一2 ) 2 1 ，如果，( 一2 ) = ，( 一2 ) = 1 ， 我们定义h 2 x 使得 h 2 ( v ) = 则( 2 ) 妒( ，) ，矛盾 ，( + 2 ) = 1 ( 3 3 ) 不妨设班n 锄，识 h 3 x 使得 h s ( v ) = 1 ， 2 肌。一3 ，z o + 1 ； 0 ， 2 蚍。一2 ，$ 如； ，( u ) ，其它 因而我们有，( z 。一2 ) + ，( 一2 ) = 1 同理，0 + 2 ) + i o 一2 s 口+ 2 ) = x l o - 2 ，+ 2 ) ，我们定义 1 ， 口= 们。一1 ，x i o + l 0 ， 口= o i o ，y i o ； ，扣) ， 其它 则( h 3 ) ( 门，矛盾因此任给1 兰i n 一3 ，我们有，( z ) + ( w ) 曼1 ( 4 ) 若，( z 1 ) = ，( 讥) = 0 ，则有，( z 2 ) = f ( y 2 ) = 1 ，矛盾因此不妨设，p i ) = 0 ，( w ) = 1 我们有f ( x 2 ) 十，) = 1 假设f ( x 2 ) = 0 ，劬) = l ，如果，( 3 ) = ，( 抛) = 0 ，则有，( 。4 ) = f ( y 4 ) = 1 ，矛 盾因此我们有，( z 3 ) + ，) = 1 。我们定义k x 使得 地( ”) = 则陬) ( ，) ，矛盾 i1 ，口= x 2 ，y 4 ； 0 ， 2y 2 ，z 3 ，船，0 4 ； l l ，o ) ， 其它 因此我们有，( z 2 ) = 1 ，f ( v 2 ) = 0 ，lli，、ii、 迥直态堂塑主兰垡迨塞 1 5 ( 5 ) 若( x s ) + ，) = 1 ，我们定义h s x 使得 f ， 一驰； h s ( v ) = 0 ，口= 奶，y 3 ； i ，( 。 其它， 则庐慨) ( ，) ，矛盾因此，( z 3 ) = ( y s ) = 0 ( 6 ) 显然f ( y 4 ) = 1 ( 否则始为未防御点) 那么f ( x 4 ) = 0 若f ( x 5 ) = 0 ，则我们只 能从驭调动军团来保卫$ 4 ，使得船成为未防御点因此，0 5 ) = 1 ，f ( y 5 ) = o ( ”如果f ( z 6 ) = f ( y 6 ) = 0 ，考虑到我们必须从粕调动军团来保卫孔，而且不能 使z 6 成为未防御点因此f ( x 7 ) = ，西) = 1 ，矛盾因而f ( m 6 ) + f ( v 6 ) = 1 假设f ( x 6 ) = 1 ，f ( y 6 ) = 0 ，如果，( 。7 ) = ，( 们) = 0 ，则有f ( x 8 ) = f ( v s ) = 1 ，矛 盾，因此我们有f ( x 7 ) + f ( y 7 ) = 1 我们定义k x 使得 ft ，u = 蜘，z s ； 蚝( 。) = 0 ，口= $ 6 ，研，斩，y s ； i ，( ”) ， 其它 则( k ) ( ，) ，矛盾因此我们有f ( x 6 ) = 0 ，f ( y 6 ) = 1 ， ( 8 ) 设h = g 一 戤，挑：1 t 4 ) 则有乃( 硼= t n y ( 日) ，n y ( 日) ，耽n y ( 日) ) 是日的个弱罗马控制函数而且我们有( ( h ) ) = ( ，) 一3 s 【竽j 一3 = 【堑；旦j ，与n = l i n 巴：竹( g 2 ，t ) 【挈j + 1 下面由图1 的构造我们证明： * ( a 2 ，。) 引甬+ l 事实上，设g 2 ，。的顶点集合y 为协，瓠：l i ，设u = ：t 茎氇 5 0 ，2 ，5 ( r o o d 8 ) 1 3 肌：i n ， ；1 ，4 ，6 ( m o d 8 ) ， 定义f = ( r o ，h ，) 如下： 当n j0 ，3 ( m o d 8 ) 时，令h = ( u u 一1 ，) ) z 。) 当t i i4 ，7 ( m o d 8 ) 时， 令= u t j z 。) 当n i1 ，2 ，5 ，6 ( m o d 8 ) 时，令k = 阢 1 6 煎宣盔堂堡圭堂焦迨塞 令= 0 令g o = v 则有”( ，) = 【警j + 1 ，而且，是g 2 。的一个弱罗马控制函数 因此命题得证口 5 4 2 弱罗马控制数的上下界 e j c o c k a y n e 3 等给出了很多罗马控制的性质，例如命题3 1 1 3 ，命题3 2 【3 ，命题 a 3 1 3 】等，并且m a h e n n l n g 1 1 等也给出了一些弱罗马控制的性质，例如命题3 1 7 i ， 命题3 1 s l l 】等作为补充，我们将给出图的弱罗马控制的一些性质以及弱罗马控制 数的上下界 命题5 设，= ( v o ，h ，k ) 是图g 的一个* ( g ) 一函数则： ( a ) 设s = u ，则对任意的口k ，肼( ”，s ) 导出一个团； ( b ) 设s = k u ，若9 v o ，d ( 如) = 2 ，口l 如，u 2 v o 曰( g ) ，n u l j 一 铀) 和 阻2 卜 v o ) 导出个团并且