（应用数学专业论文）与树的罗马控制有关的一个小问题.pdf

河南大学硕士学位论文 摘要 定义在v 上的一个实值函数。，：v ， 0 ，1 ，2 ) 称为图g = ( ve ) 的一 个罗马控制函数，如果中的每一个顶点至少与k 中的一个顶点相邻，其中 对于i = 0 ，l ，2 ，= f 让：f ( u ) = ，是y 中赋值为i 的顶点集合对于y 的任 意一个了集s ，我们定义y ( s ) = 口s 厂( u ) ，并且我们定义厂的权为加( 厂) = y 厂( u ) 图g 的罗马控制函数的最小权称为罗马控制数，记为垤( g ) 如 果t 是一个树且l y ( 丁) l 2 ，那么q r ( t ) = 7 ( t ) + 1 当且仅当t 是一个病态蜘 蛛树在该篇论文我们主要研究满2 = t r ( t ) = 7 ( t ) + 2 $ 1 b ( t ) nc ( t ) 仍的 树t 的结构性质 关键词：罗马控制罗马控制数树 河南大学硕士学位论文 a b s t r a c t ar o m a nd o m i n a t i o nf u n c t i o no nag r a p hg = ( y ，e ) i saf u n c t i o n f ：v 叫 o ，1 ，2 ) s a t i s f y i n gt h ec o n d i t i o nt h a te v e r yv e r t e xi nv 0 i sa d - j a c e n tt oa tl e a s to n ev e r t e xi n ，w h e r ei = 0 ，1 ，2 ，k = 扎：f ( u ) = 讲 f o re a c hscv ，w ed e f i n e ( s ) = 口s 厂( 秒) ，t h ew e i g h to far o m a nd o m - i n a t i o nf u n c t i o ni st h ev a l u e 叫( 厂) = y ，( ) ，t h em i n i m u mw e i g h to f ar o m a nd o m i n a t i o nf u n c t i o no nag r a p hg ，d e n o t e d 垤( g ) ，i sc a l l e dt h e r o m a nd o m i n a t i o nn u m b e ro fg ，i fti sat r e eo nt w oo rm o r ev e r t i c e s ，t h e n ( t ) = 7 ( t ) + l i fa n do n l yi ft i saw o u n d e ds p i d e r i nt h i sp a p e r ，w e s t u d yt h ep r o p e r t i e so ftw i t h7 r ( t ) = 7 ( t ) + 2a n db ( t ) nc ( t ) 0 k e y w o r d s ：r o m a nd o m i n a t i o n ， r o m a nd o m i n a t i o nn u m b e r ，t r e e i i 关于学位论文独立完成和内容创新的声明 本人向河南大学提出硕士学位中请。本人郑重声明：所呈交的学位论文是 本人在导师酌指导下独立克成的，对所研充的课题有新i 均见解。据哦所知，除 文中特别加雕说明、标注和致谢的地方外，论文中不包括其他人已经发表或撰 写过的研究成果，也不包括其他人为薮得任何教育、科研机构的学住或证书而 使月过的材料。与我一同工作的同事对本研究所儆的任何贡献均已在论文中作 了明确酌说明并表示了谢意。 学位申请人( 学位论文作者) 篓名： 卸哆卑6 月，o 目 关于学位论文著作权使：用授权书 本人经河南大学审核批准援子硕士学位。作为学位论文的作者，丰人完全 了解并同意河南大学有关保留、使用学值论主韵要求，雾p 河南大学有权向国家 图书馆、科研信蝴| 枸、数据收集机构和本校图书馆等提供学位论文( 羝质文 本和电子文本) 皑供公众检索、查阅。本 授权河南大学出于宣扬、展览学校 学术发展和进行学术交流等目的，可阱采取影印、缩印、扫描和拷贝等复制手 段保存、汇编学位论文( 氟质文本和电子文本) 。 ( 涉及保密内容的学位论文在解密后适用本授权书) 学住获得者( 学位论文作者) 签名： 2 0 学位论文指导教师釜名： 2 0 室壹堑 乓6 受| 鼋 第一章引言 c o c k a y n e 等在f 3 1 中给出了在一个图g = ( ve ) 上的罗马控制函数( 简 称r d f ) 的定义：定义在y 上的一个函数厂：vh _ f0 ，1 ， 2 称为 图g = ( ve ) 的一个罗马控制函数如果它满足：每一个使f ( u ) = o 的顶 点u 至少连接一个顶点u 使f ( v ) = 2 实值函数f ：vh 同拘权记为叫( 厂) = 。y 厂( u ) ，并且我们定义f ( s ) = 钉s 厂( ) ，v s y ，因此叫( 厂) = 厂( y ) 图g 的罗马控制函数的最小权称为罗马控制数，记为7 r ( g ) ，也 即恤( g ) = m i n w ( f ) l f 是g 的一个r d f 一个权为垤( g ) 的r d f 我们叫做 一个伽( g ) 一函数图的罗马控制的一些理论性质在3 ，4 ，6 ，1 0 1 中已经被 很好的研究过 定义罗马控制函数的意图来源于i a ns t e w a r t 在美国科学杂志上发表的 一篇题为“防御罗马帝国! ”f 1 1 】在我们所研究的图中的每一顶点代表罗马 帝国的一个地区一个地区( 顶点u ) 被认为是不安全的如果没有军队驻扎在 那里( 即厂( u ) = o ) ，否则被认为是安全的( 即厂( u ) 1 ，2 ) ) 一个不安 全的地区( 顶点v ) 能够被安全防御如果能够从相邻的地区( 口的一个邻点札) 派 一支军队到达该地区但是在公元四世纪最高统治者颁布法令：一支军队 不能从一个安全地区派遣到一个不安全的地区如果派遣后使得该地区不安 全因此，在派出其中一支军队到相邻地区之前必须在该地区驻扎两支军 队( 厂( 口) = 2 ) 最高统治者利用这种方式能够防御罗马帝国因为在一个地 区给养一支军队是很昂贵的，所以统治者想用尽可能少的军队防御罗马帝 国一个权为伽( g ) 的罗马控制函数对应着一个最优分派部队驻扎的方案 为探究节约统治者基本的给养军队的花费，同时仍然能够防御罗马帝国 的潜力，m a h e n n i n gf 1 1 等提出了新的策略令g = ( ve ) 是一个图，厂是 一个函数厂：vh o ，1 ，2 ) 设，k 分别代表在厂作用下取值分别 为0 ，1 ，2 的顶点集注意到在函数厂：yh _ 【0 ，1 ，2 ) 和顶点u 的划分( ， ，) 之间存在一一对应关系因此我们记厂= ( y o ， ， k ) 本文主要围绕图的罗马控制展开讨论，研究了满足 7 r ( t ) = 7 ( t ) + 2 和b ( t ) nc ( t ) d 的树t 的结构性质 1 第二章记号 在本文中，所考虑的图均为有限的非平凡简单图对于图g ，v = y ( g ) 和 e = e ( g ) 分别表示它的顶点集和边集设s y ，集合( s ) = u v s ：存在一个v s 使得u v e ，集合 翻= su ( s ) 对于讹 vg ( v ) = u v ：u v e ) 并且m = g ( v ) u u ) ，d ( 钞) 表示 图g 中顶点v 的度一个顶点乱被称为v 关于s 的私有邻点，或简单的说是v 的 一个s m 如果mns = v ) 顶点v 的所有s 一册的集合册( u ，s ) = n v 1 一n s 一_ 【钉1 1 被称为u 关于s 的私有邻集我们定义口关于s 的外私有 邻集为e p n ( v ，s ) = m ( u ，s ) 一 u ) 设s y 我们说集合s 控制集 合u ，记为s u ，如果u s 中的每一个顶点至少邻接s 中的一顶点如 果s - y s 或者等价地，司= v ，则s 被叫做g 的一个控制集图g 的 最小控制集的基数称为最小控制数，记着7 ( g ) 一个基数为7 ( g ) 的控制集称 为7 ( g ) 一集图的控制集f 7 1 以及它的变化形式目前己经有了很好的研究特 别地h a y n e s e t a l 8 ，9 1 给出了有关这一主题的深入调查和研究 我们称图g 是罗马图如果伽( g ) = 2 7 ( g ) 一个顶点集合s 被称为独立的如果s 中的任意两个顶点均不相邻图g 的 独立控制集( 或者等价地，图g 的最大独立集) 的最小基数称为独立控制数， 记着z ( g ) 一个顶点集合s 被称为2 一分离的如果g u 】nn v 】= 仍，v u ，y e s 图g 的 最大2 一分离集的基数称为2 一分离数，记着p 2 ( g ) 一个顶点集合s 被称为点覆盖集如果v u v e ，要么乱s 要么v s 罗马控制f 1 1 的引入具有历史意义和数学兴趣定义在v 上的一个实值函数厂：v f 0 ，1 ，2 ) 称为图g = ( ke ) 的一个罗马控制函数，如果每一个赋值 为0 的顶点都至少与一个赋值为2 的顶点相邻对于图g = ( ve ) ，设厂是 它的一个罗马控制函数，( ，k ) 是在厂f y 的一个划分其中对于i = o ，1 ，2 ，k = u ：- 厂( u ) = i ) 是y 中赋值为i 的顶点集合，记作f = ( v o ，k ) 设i k i = 啦，则厂的权记作，= 。y 厂( 秽) = 2 n 2 + 7 2 1 图g 的罗马控制函数 的最小权称为罗马控制数，记为，y r ( g ) 也即 7 n ( c ) = m i n w ( f ) l f 是g 的个r d f ) 一个权为垤( g ) 的罗马控制函数 2 河南大学硕士学位论文 我们叫做一个，y r ( g ) 一函数 对于图g ，设 a ( g ) = u s v ( a ) ：s 是g 的一个，y 一集 - b ( a ) = u k v ( a ) ：，= ( v o ，k ) 是一个7 r ( g ) 函数) c ( a ) = u v ( g ) ：7 ( g 一钉) = 7 ( a ) 一1 d ( a ) = u v ( g ) ：7 n ( g u ) = 7 n ( g ) 一1 对于任给的正整数t ，完全二部图甄，t 称为星，并且称度为( t 2 ) 的顶 点为中心点，度为1 的顶点为外点，而情形马中，我们称两个顶点都为中心 点一个病态的蜘蛛树是指一个星k 1 。至多剖分它的t 一1 条边类似地，对 于任给整数t 2 ，一个健康的蜘蛛树是指一个星k 1 。剖分它的所有边在 一个病态的蜘蛛树中，一个度为t 的顶点将被称为头点，并且与头点的距离 为2 的顶点称为脚点头点和脚点是确定的除非当病态的蜘蛛树是两个或四 个顶点的路对于恳，我们将规定两个顶点都为头点，而情形只中，我们将 规定两端的顶点都为脚点，并且两个中间点都为头点相似的，在一个健康 的蜘蛛树中度数为t 的顶点称为它的头点，并且与头点的距离为2 的顶点称为 脚点注意到，由于t 2 ，在一个健康的蜘蛛树中，头点和脚点是确定的见 图2 1 c 矗 图2 1病态的蜘蛛树( a c ) 和健康的蜘蛛树( d ) 3 第三章相关的已知结果 关于图的罗马控制已经有了很多的结论，本章主要是把与本文有关的 结论列出来，以便后面使用 命题3 1 1 3 】对任何阶数为n 的图g ，7 ( g ) = 垤( g ) 当且仅当g = 瓦 命题3 2 3 设厂= ( y o ，) 是任何垤一函数，则 ( a ) 由导出的子f 訇a y 1 的最大度为1 ； ( b ) m 和之间没有边相连； ( c ) y o 中的每一个顶点至多与m 中的两个顶点相邻； ( d ) k 是g uk 】的一个r 集； ( e ) 设h = g y ouk 】，则的每一个顶点v 至少有两个一肌( 即图日中关 于k 的私有邻点) ； ( f ) 如果v 是g 【k 】的孤立点并且仅有一个外日一m ，记为伽，贝, m j n ( w ) n = d ： ( g ) 设七为g k 中非孤立点数目，令c = _ ( v | i n ( v ) n i 2 ) 且l c i = c ，则礼o n 2 + k + c 命题3 3 3 设厂= ( y o ，y l ，) 是无孤立点图g 的一个一函数，使 得n ，最小则： ( a ) 是独立集且u 是一个覆盖； ( b ) 卜； ( c ) y o 中的每一个顶点至多邻接中的一个顶点，即是一个2 一分离集； ( d ) 设v c i v i l 恰有两个外一册，记为叫1 ，w 2 y o ，则不存在点可1 ，y 2 使得( y l ，w l ，口，w 2 ，耽) 是一条路r 的顶点序列； ( e ) 扎o 3 n 7 ，并且这个界是紧的 命题3 4 3 】对任何阶数为n 且最大度为的图g ， 急伽( g ) 1 一( v n i ，：l + 一“u 一7 命题3 5 3 对任何阶数为n 的图g ， 椰胁半筹 ，j 、一，一 1f ，t 、 4 河南大学硕士学位论文 命题3 6 3 】( r ) = 7 r ( c n ) = 等 命题3 7 3 】设g = k n ，仇。，m 。是完全佗一部划分图， 并且使得m 1 仇2s sm n 则： ( a ) 女口果7 n 1 3 ，贝0 ，y r ( g ) = 4 ； ( b ) 如果m 1 = 2 ，贝, u t r ( g ) = 3 ； ( c ) 如果m 1 = 1 ，则恤( g ) = 2 ； 命题3 8 3 】如果g 是一个阶数为n 且包含一个佗一1 度的顶点的图，则 1 ( g ) = i 且t r ( g ) = 2 命题3 9 3 对任何2 礼格图g 2 ，n ，7 r ( g 2 ，n ) = 几+ 1 命题3 1 0 1 3 1 如果g 是阶数为n 的无孤立点的图，贝, u t r ( g ) = n 当且仅 当佗是偶数且g ：n 。k 2 ，其中昙鲍代表昙个的拷贝 命题3 1 1 1 3 】如果g 是一个阶数为他的连通图，则t r ( g ) = 7 ( g ) + 1 当且 仅当存在v v 使得d ( v ) = 礼一，y ( g ) 命题3 1 2 1 3 如果t 是一个非平凡树，则垤( t ) = 7 ( t ) + 1 当且仅当丁是 一个病态的蜘蛛树 命题3 1 3 1 3 g 是一个阶数为n 的连通图，贝o t r ( g ) = 7 ( g ) + 1 当且仅当： ( a ) g 不含度为佗一7 ( g ) 的顶点； ( b ) a 有一个度为n 一，y ( g ) 一1 的顶点或者有两个顶点u 和伽使得i n v u n w i = 礼一7 ( g ) + 2 命题3 1 4 1 3 】图g 是罗马图当且仅当它有一个恤一函数，= ( y o ，k ，) 使 得 礼1 = l i = 0 a i 命题3 1 5 3 】图g 是罗马图当且仅当7 ( g ) 7 ( g s ) + 等， 对每一 个2 一分离集s y 命题3 1 6 1 3 】如果t 是一个至少有两个顶点的树，则他( t ) = 7 ( t ) + 1 当 且仅当丁是一个病态蜘蛛树 命题3 1 y 4 如果g 是一个阶数为n 的连通图，则垤( g ) = 7 ( g ) + k 当 且仅当： ( a ) v l j k 一1 ，g 不含一个阶数为歹的子集s y 使得 i 【司l n 一( ，y ( g ) + i ) + 2 j ：jsi 南一1 ) 5 河南大学硕士学位论文 ( b ) c 含有一个子集岛y 使1 f s o f 七h - i n s o 】j = 礼一( 7 ( g ) + 七) + 2 1 s 0 1 命题3 1 8 1 4 1 如果t 是通过五和死之间增加一条边u 1 2 构成的简单连通 图，其中u 1 y ( 丑) ，钐2 y ( 乃) ，那么我们有下面的结论： ( a ) 7 r ( 乃) + - y , t ( t 2 ) 一7 r ( t ) _ o ，1 ) ，- y ( t 1 ) + - y ( 疋) 一- y ( 7 ) o ，1 ) ( b )若u 1 b ( 7 1 ) 且 y r ( t 2 一u 2 ) = y r ( t 2 ) 一1 ，那么恤( t ) = y r ( t 1 ) + 垤( 正) 一1 若u 1gb ( r 1 ) 且 y r ( t 1 一秒1 ) y r ( t 1 ) ，那么7 r ( t ) = 7 r ( t a ) + - y r ( r 2 ) 若v lgb ( r 1 ) 月- v 2gb ( 乃) ，那么7 r ( t ) = 他( 丑) + ( 死) 若垤( 五一u 1 ) - y , i ( r 1 ) 且, y r ( r 2 - - v 2 ) y r ( t 2 ) ，那z , y r ( r ) = y r ( t 1 ) + ，y r ( 乃) ( c )若7 3 1 a ( 7 1 ) 且，y ( 疋一v 2 ) = - y ( 疋) 一1 ，那么- y ( 7 ) = - y ( 丑) + ，y ( 乃) 一1 若移1ga ( 乃) 且7 ( 7 1 一 1 ) ，y ( 7 1 ) ，那么- y ( t ) = - y ( 五) + - y ( 足) 若秒1za ( t a ) 且 2ga ( 疋) ，那么- y ( t ) = 7 ( t 1 ) + 7 ( t 2 ) 若- y ( t 1 7 3 1 ) - y ( 五) 且7 ( 易一u 2 ) - y ( 正) ，那么7 ( t ) = - y ( 7 1 ) + ，y ( 疋) 命题3 1 9 1 4 】如果t 是一个有确定头点u o 的病态蜘蛛树，并且，是它的垤一 函数，那么我们一定有厂( o ) = 2 命题3 2 0 4 如果t 是一个以如为头点的健康蜘蛛树，l y ( t ) l 5 并且厂是 它的垤函数，那么我们一定有y ( v o ) = 2 命题3 2 1 1 1 2 】t 是一个阶数为n ( 2 ) 的树，且存在t 的一个罗马控制函 数厂= ( v o ，k ) 使得i k i = 1 且是一个2 一分离集，那么丁是健康或病态 的蜘蛛树 命题3 2 2 4 】树t 满足7 r ( t ) = - y ( t ) + 2 当且仅当下列条件中至少一个成 立： ( i ) ：丁是一个健康的蜘蛛树 ( i i ) ：t = ( y ( t ) ，e ( t ) ) = ( y ( 五) u v ( t 2 ) u v ( r ) ，e ( t 1 ) u e ( t 2 ) u e ( e ) ) ， 其中1 i 7 ，并且乃是以让，为头点的病态蜘蛛树j = 1 ，2 ，而且t 不是病 态的蜘蛛树 ( i i i ) ：t = ( y ( t ) ，e ( t ) ) = ( y ( 互) u y ( 乃) u y ( 忍) ，e ( 7 1 ) u e ( t 2 ) u e ( 只) ) ， 其中乃是以u ，为头点的病态蜘蛛树，易是以u 2 为头点的健康蜘蛛树 命题3 2 3 1 1 3 ：对于任意1 i m = 由( 如) ，设互是t 一咖中包含仇的分 支，其中u ( v o ) = 仇：1 i m ) 那么我们有以下结论： ( a ) 一m + 2 7 r ( t ) 一墨1 垤( 正) 1 ，一仇+ l 7 ( 丁) 一銎17 ( 正) 1 6 河南大学硕士学位论文 ( j e 7 ) 设x = i k ：v i d ( 互) ) ，y = z k ：v i b ( 正) ) 那么： 垤( t ) = e 警1 ( 互) + 1 当且仅当l x l 1 且y = 0 7 r ( t ) 銎17 r ( 正) 当且仅当i x l 2 对于任意k 一2 ，恤( t ) = e 任r n1 仇( 五) 一当且仅当l x l = + 2 ( c ) 设z = 【i k ：v i c ( 正) ) ，w = i k ：仇a ( 互) ) 那么： 7 ( t ) = 2 17 ( 正) + 1 当且仅当z = w = 0 - y ( t ) 扛m1 ，y ( 正) 当且仅当i z i 1 对于任意七厶一2 ，7 ( t ) = 诘m 1 - r ( t i ) 一尼当且仅当i x i = k + 1 命题3 2 4 1 1 3 1 设正是t 一 g o 的一个分支，让o d ( t ) i 马v ( t ) 3 ，设g i = 丁【y ( 五) u 乱o ) 】那么u 0 d ( g 1 ) ，y ( 丑) 3 命题3 2 5 1 1 3 】设互是t 一 g o 的一个分支且珏o c ( 丁) ，设g 1 = t v ( t 1 ) u 乱o 那么u o c ( g i ) ，v ( 乃) 3 命题3 2 6 1 1 3 设t 是一个满足伽( t ) 7 ( t ) + 2 的树且u o b ( 丁) ，那 么u oga ( t ) 当且仅当t 是一个健康的蜘蛛树 命题3 2 7 1 1 3 树t 满足垤( t ) = 7 ( t ) + 3 当且仅当下列条件中至少一个 成立： ( i ) t = ( y ( t ) ，e ( t ) ) = ( y ( 乃) uy ( t 2 ) uy ( 只) ，e ( 互) ue ( 死) ue ( 只) ) ， 其中1 i 7 ，互是以u 1 为头点的病态蜘蛛树，恤( 易) 7 ( 正) + 2 且札2 b ( 死) 而且恤( t ) 7 ( t ) + 2 ( i i ) t = ( y ( 丁) ，e ( t ) ) = ( y ( 正) u y ( 死) u v ( f 2 ) ，e ( 丑) u e ( t 2 ) u e ( 尼) ) ， 其中互是以“f 为头点的健康蜘蛛树，j = 1 ，2 ( i i i ) t = ( y ( t ) ，e ( t ) ) = ( y ( 丑) u v ( t 2 ) u v ( f 4 ) ，e ( 五) u e ( t 2 ) u e ( f 4 ) ) ， 其中乃是以u 1 为头点的健康蜘蛛树，7 r ( t 2 ) = 7 ( 正) + 2 且u 2 b ( 乃) ( i v ) t = ( y ( t ) ，e ( t ) ) = ( y ( 丑) u v ( t 2 ) u y ( 只) ，e ( 五) u e ( t 2 ) u e ( 只) ) ， 其中z = 3 ，8 ，9 ，1 0 ，1 1 ，对于j = 1 ，2 ，3 ，乃是以为头点的病态蜘蛛 树而且如果j = 3 ，1 1 有i y ( 乃) i 3 ( v ) t = ( y ( t ) ，e ( t ) ) = ( y ( 丑) u y ( 噩) u y ( 只) ，e ( 五) u e ( 马) u e ( r ) ) ， 其中t = 8 ，9 ，冗是以让1 为头点的健康蜘蛛树对于j = 2 ，3 ，乃是以嘶为 头点的病态蜘蛛树 ( v i ) t = ( y ( t ) ，e ( t ) ) = ( y ( 乃) u v ( t 2 ) u v ( 日) ，e ( 正) u e ( t 2 ) u e ( 乃) ) ， 其中 = 8 ，9 ，五是以u 1 为头点的病态蜘蛛树，并且他( 死) = 7 ( 正) + 弋 河南大学硕士学位论文 2 ，d ( u 2 ) = 2 ，u 2 b ( t ) ，u 2ga ( t 2 ) ub ( t 2 ) 而且，v 2 c ( t ) nd ( t ) 以上所涉及的只( 1 i 1 1 ) 定义如下图： “ ，塑碧善2 2 u “舌氅塑錾2 ， u 图3 1 8 2 2 第四章主要结果的证明 4 1 主要结果 对于满足7 r ( t ) = 7 ( t ) + 2 的树t 我们可以用下面的命题对它的性质进 行刻划： 定理4 0 设t 是满足7 r ( t ) = 7 ( t ) + 2 的树，那么b ( t ) nc ( t ) 0 当且仅当： t = ( v ( t ) ，e ( t ) ) = ( v ( t o ) u a ，b ，c ，d ) ，e ( t o ) u a b ，b c ，c d ，b u o ) ， 其中乃是以u o 为头点的病态蜘蛛树，且i v ( t o ) i 2 ( 见图1 ) 图l 4 2 几个引理 为了证明上述结论，我们先来证明以下引理 引理4 1 若丁是一个健康的蜘蛛树，那么c ( t ) = 0 ( 见图2 ) 证明：设v ( t ) = 钆o ) u 缸t ：1 i 七) o v j ：1 j 七 ， 9 河南大学硕士学位论文 e ( t ) = u o u i ，u i v i ：1 i 尼) ， k 2 则有7 ( t ) = 7 ( t 一札o ) = ，y ( t u 1 ) = 7 ( t v 1 ) = k ，贝j j c ( t ) = 仍，引理4 1 i f f _ 毕 功 功 磁 图2 引理4 2 如果t 是以u o 为确定头点的病态蜘蛛树，而且t 不是长为1 、2 、3 的路，那 么7 s ( t v 0 ) 3 r ( t ) + 1 证明：设m 和礼分别表示t 的健康的腿数和断腿数，由于丁不是长为1 、2 、3 的 路，因此m + n 3 ，而且佗1 则有7 r ( t ) = m + 2 ，7 r ( t v 0 ) = 2 m + n = 7 r ( t ) + m - i - 佗一2 7 r ( t ) + 1 ，引理4 2 证毕 引理4 3 设t - - ( v ( t ) ，e ( t ) ) = ( y ( 五) uy ( 正) uy ( 最) ，e ( 丑) ue ( 正) u e ( 乃) ，其中正是以让1 为头点的病态蜘蛛树，t 2 是以乱2 为头点的健康蜘蛛树 那么b ( t ) n c ( t ) = d ( 见图3 ) 1 0 河南大学硕士学位论文 t 。t ， 图3 证明：设k = “1 ，u 2 ) ，v o = 坼( ) ，= v 一爵( k ) ， 则 有f = ( y o ，) 是丁的一个罗马控制函数设 一, - t - ( y ony ( 五) ，ny ( 五) ，kny ( 乃) ) 和厶= ( y o n y ( 正) ，n v ( t 2 ) ，k n y ( 马) ) ， 则t 厂( y ( 丁) ) = ( y ( 五) ) + 止( y ( 乃) ) = 垤( 丑) + ，y r ( 正) = 7 ( 乃) + 7 ( t 2 ) + 3 = 7 ( t ) + 2 = 恤( t ) ，则有f = ( y o ，) 是树t 的一个7 r ( t ) 西j 数从而 可以得到，让1 ，u 2 b ( t ) 下证b ( t ) = u l ，钆2 ) ， 设f = ( x o ，x 1 ，托) 是树丁的一个伽一函数我们只需证明x 2 = 乱1 ，u 2 ) 即可 假设有x x 2 并且z u 1 ，u 2 由于7 r ( t ) = ，( y ( t ) ) = i x l l 十2 1 x 2 f = 7 ( t ) + 2 i x l i + i 恐i + 2 ，则有i 也i 2 因此，钆1 ，u 2 两点至少有一点不 在磁中 设t 3 = t y ( 丑) ，t 4 = t y ( t 2 ) 对于j = 1 ，2 ，3 ，4 ，我们设 f j = ( x ony ( t j ) ，x 1ny ( 乃) ，nv ( t a ) ， 其中乃是一个健康的蜘蛛树，乃是一个病态的蜘蛛树我们分以下两种情况 讨论： c a s e1 f ( u 1 ) 1 此时 是乃上的一个罗马控制函数，我们有 河南大学硕士学位论文 7 r ( t ) = 厂( y ( t ) ) = ( y ( 冗) ) + ( y ( 死) ) ( y ( 丑) ) + 恤( t 3 ) = ( y ( 乃) ) + 7 r ( t 2 ) + 1 = ( y ( 乃) ) + 7 n ( t ) 一( 五) + 1 则有 ( y ( 乃) ) 7 r ( t 1 ) 一1 ，即 不是丑上的一个罗马控制函数 因此我们有f ( u z ) = o 和f ( v z ) = 2 ，其中n ( u 1 ) ny ( t 3 ) = u ，) 乃是一个 以u 2 为头点的健康蜘蛛树，由命题3 2 0 可知，厶不是死的一个最优罗马控制 函数，则有 ( y ( 死) ) 7 n ( t 3 ) + 1 ，则 ( y ( 丑) ) = ，( y ( t ) ) 一 ( y ( 死) ) 7 n ( t ) 一7 n ( t 3 ) 一1 = 7 n ( t ) 一7 n ( t 2 ) 一2 = 7 n ( t 1 ) 一2 ，但是由于 爿= ( ( ny ( 互) ) 缸) ，x 1ny ( 正) ，托ny ( 丑) ) 是乃一u l 上的一个罗 马控制函数，则有 7 r ( t 1 ) 一2 ( y ( 乃) ) = 爿( y ( 丑一u 1 ) ) 7 s ( t 1 一钆1 ) 显然矛盾 c a s e2 f ( u 2 ) 1 此时厂4 是乃上的一个罗马控制函数，我们有： 7 r ( t ) = 厂( y ( t ) ) = ( v ( t 2 ) ) + ，4 ( y ( 乃) ) 如( y ( 乃) ) + 垤( t 4 ) = 止( y ( 马) ) + 7 r ( t 1 ) + 1 = a ( y ( 死) ) + 伽( t ) 一7 r ( t 2 ) + 1 因此有止( y ( 易) ) 7 n ( t 2 ) 一1 ，即如不是乃上的一个罗马控制函数， 则有f ( u 2 ) = 0 ，而且尼= ( ( x ony ( 乃) ) u 2 ) ，x 1ny ( t 2 ) ，x 2ny ( 易) ) 是t 2 一u 2 上的一个罗马控制函数则有 7 r ( t 2 ) 一1 ，2 ( y ( 正) ) = 彤( y ( 正一u 2 ) ) 7 n ( t 2 一u 2 ) 由于乃是健康的蜘蛛树，得出矛盾 从以上两种情况我们可以得出b ( t ) = u 1 ，u 2 】i - f ：i i f b ( t ) nc ( t ) = d 我们对u l ，u 2 分别讨论： ( i ) 假设让1 c ( 丁) ，我们有7 ( t - u 1 ) = - y ( 死) + m 1 + 佗1 = 7 ( t ) 一1 ，( 其 中m 1 ，n ，分别表示乃的健康的腿数和断腿数) 从而7 ( 丁) = 7 ( 死) + 仇1 + 佗1 + 1 但由于z ( t ) 7 ( 乃) + 7 ( 死) m 1 + 1 + ，y ( 死) ， 可得n 1 = 0 ，从而得出矛盾因此假设不成立，我们有u 1gc ( t ) ( i i ) 假设u 2 c ( t ) ，我们有7 ( t 一7 1 2 ) = ，y ( 丁) 一1 ，并且有7 ( t 一札2 ) = 7 ( 丑) + m 2 ，其中仇2 为乃的腿数而7 ( 印= ，y ( 五) + 7 ( 正) + 1 ，7 ( 五) = 1 2 河南大学硕士学位论文 7 ( 乃) + 1 ， 所以7 ( t ) = ，y ( 丑) + 7 ( 乃) = 7 ( 乃) + m 2 这样就有7 ( t u 2 ) = 7 ( t ) ，得出 矛盾 由( i ) ，( i l ) 可得u l ， 2 都不属于c ( 丁) ，所以b ( t ) n c ( t ) = 0 引理4 3 证 引理4 4 设t 是满足7 r ( t ) = 7 ( t ) + 2 的树，而且t 不是健康的蜘蛛树，则我们能 够找到一个伽( t ) 一函数厂= ( ) t o ，x l ，恐) ，使得i x 2 l = 1 ，当且仅当下述几 种情况中至少一种情况成立： 情形1 ：t = ( y ( t ) ，e ( t ) ) = ( y ( t a ) l j 钍o ， v 0 ，叫o - ，e ( 丑) u y o u l ，u o v o ，u o w o ) ) ，其中乃是以乱l 为头点的病态蜘蛛树，五不是长为1 的 路( 见图4 ) 情形2 ：t = ( y ( t ) ，e ( t ) ) = ( y ( 乃) l j ，v o ，w o ，e ( 五) u u o u l ，u o v o ，u o w o ) ，其中乃是以u 1 为头点的病态蜘蛛树，五不是长为1 的 路( 地图5 ) u ， 谅 、 t 】 图4 眦 弛 雨 证明：充分性显然下证必要性 设，= ( x o ，x 1 ，恐) 是一个他( t ) 函数，使得x 2 = u 1 ) ，则x 1 中的每一 个点都是1 度点或者2 度点，而且对于任意凰中的每个顶点至多与两个赋值 1 3 河南大学硕士学位论文 为1 的顶点相邻 设w 1 = z x 1 ：l ( z ) i = 2 ) 和w 2 = z x o ：l n ( x ) nx 1 i = 2 】- ， 己知t r ( t ) = ，y ( t ) + 2 ，则丁不是一个病态的蜘蛛树 如果肌= w 2 = d ，则x 1 中每个顶点都是1 度点，而且中每个顶点都 是2 度点，n t 是一个健康的蜘蛛树，从而得出矛盾 如果l 肌i 2 ，设u 2 ，u 3 m ，n ( u 2 ) = v 2 ，叫2 ) ，n ( u 3 ) = v 3 ，伽3 ) ， 其中t 厂( z ) = f ( v 3 ) = 0 ，厂( 乱2 ) = 厂( u 3 ) = f ( w 2 ) = f ( w 3 ) = 1 ，( 见图6 ) 优 u 2 w 2 图6 仍 u 3 眺 图8 图7 7 设死= t 一 v 2 ，u 2 ，w 2 ，u 3 ，v 3 ，伽3 ) ，w 3 = u 1 ，u 2 ，u 3 u ( x 1ny ( 死) ) ，贝 j w 3 是t 的一个控制集，从而有： 7 ( t ) i w 3 l = 3 + l 五i 一4 = i 蜀f 一1 ，7 r ( t ) = f 五f + 2 7 ( t ) + 3 ，得出矛盾 1 4 河南大学硕士学位论文 如果i 鹏i 2 ，设u 4 ，u 5 ，n ( u 4 ) = u l ，v 4 ，叫4 ，n ( u 3 ) = u l ，v 5 ，w s ，其中厂( u 4 ) = ，( u 5 ) = 0 ，厂( 啦) = 厂( 口5 ) = f ( w a ) = 厂( 叫5 ) = 1 ，( 见图7 ) 设噩= t u 4 ，v 4 ，0 4 ，u 5 ，v 5 ，w s ，w 4 = u 4 ，u 5 ) u ( x iny ( 乃) ) ， 则是t 的一个控制集，从而有： 7 ( t ) l w 4 i = 2 + f x l | _ 4 = i x i i - 2 ，垤( t ) = i x l l + 2 ，y ( t ) + 4 ，得出矛盾 如果i 肌i = l w 2 i = 1 ，设1 1 6 眠，u 7 w 2 ，n ( u o ) = v 6 ，伽6 ) ，n ( u 7 ) = 让t ，v 7 ，w t ，其中厂( ) = f ( u 7 ) = 0 ，f ( u 6 ) = ，( 叫6 ) = ，( u ，) = 厂( 训7 ) = 1 ，( 见图8 ) 设死= t 一 u 6 ，u 6 ，w 6 ，u 7 ，v 7 ，叫7 ) ，慨= u 6 ，u t u ( x 1ny ( 死) ) ， 则眠是丁的一个控制集，从而有： 7 ( t ) l w 4 i = 2 + l x i i 一4 = j x l l 一2 ，7 r ( t ) = j 蜀i + 2 7 ( t ) + 4 ，得出 矛盾 综上所述，我们有f 啊i + i i = 1 如果l 肌i = 1 ，则有i i = 0 ，情形1 成立；如果l i = 1 ，则有i 啊i = 0 ，情 形2 成立引理4 4 证毕 引理4 5 己知t = ( y ( t ) ，e ( t ) ) = ( y ( 乃) uy ( 死) uy ( 只) ，e ( 五) ue ( t 2 ) u e ( 只) ) ，其中1 i 7 对于歹= 1 ，2 ，乃是以为头点的病态蜘蛛树，而 且t 不是病态的蜘蛛树，n 和正都不是长为1 或3 的路那么b ( t ) = u l ，u 2 证明：设k = u l ， u 2 ) ，= 坼( k ) ，= v ( t ) 一v o 一， 那么厂= ( v o ，) 是t 的一个罗马控制函数我们可以断言厂( y ( t ) ) = 7 n ( t ) = 7 ( t ) + 2 事实上，我们可以设 = ( y o n y ( 丑) ，n y ( 丑) ， u ，) ) ，2 = ( v o n y ( t 2 ) ，n y ( 乃) ， u 2 ) ) ， 由于乃，死都是病态的蜘蛛树，所以由命题3 1 9 我们有，1 是伽( 互) 函数，厶是 7 r ( t 2 ) 函数由于五和疋都不是长为1 或3 的路，我们有 u lgc ( 丑) ，让2gc ( 正) ，u l 4 ( 五) ，u 2 4 ( 乃) 1 5 河南大学硕士学位论文 如果i = 1 ，我们有厂( y ( t ) ) = ( y ( 五) ) + ，2 ( y ( 疋) ) = ( 死) + 垤( 易) = 7 ( 五) + 7 ( 正) + 2 = 7 ( t ) + 2 如果i = 2 、4 ，我们有 ，( y ( 丁) ) = ( y ( 乃) ) + 止( y ( 乃) ) = 7 r ( 乃) + 伽( 易) = 一y ( 丑) + 7 ( 乃) + 2 = ，y ( t ) + 2 ，( 在这里l y ( t ) i 6 ，否则t 是一个健康的蜘蛛树) 如果i = 3 、5 、7 ，我们有 厂( y ( t ) ) = ( y ( 正) ) + 尼( y ( t 2 ) ) + 1 = 7 r ( t 1 ) + 垤( t 2 ) + 1 = 7 ( 五) + 7 ( 乃) + 3 = 7 ( t ) + 2 ( 在这里我们应注意到对- 于i = 3 有l y ( 正) l + i y ( 是) l 5 ，否 则t 是一个病态的蜘蛛树) 如果i = 6 ，我们有厂( y ( t ) ) = 7 r ( t 1 ) + 7 r ( t 2 ) + 2 = 7 ( 五) + 7 ( 疋) + 4 = 7 ( t ) + 2 综上所述，断言厂( y ( t ) ) = 他( t ) 成立，即厂是一个7 r ( t ) i 函数，从而 有u l ，u 2 j e 7 ( t ) 下证b ( t ) = u l ，u 2 设f = ( x o ，x 1 ，z 2 ) 是( t ) 一函数，由命题3 2 2 可矢i f ( v ( t ) ) = 7 r ( t ) = 7 ( t ) + 2 如果l 托i = 1 ，由引理4 4 可知恐u l ，u 2 ) 下面 证明中我们不妨设i 托i 2 我们只需证明x 2 = u 1 ，? 2 2 即可假设存在一点z 恐，而且z 钆1 ，u 2 ，由于( t ) = 厂( y ( t ) ) = l x l l + 2 1 x 2 i = ，y ( t ) + 2 i x l i + i x 2 l + 2 ， 则有l x 2 i 2 ，则i x 2 l = 2 因此札1 署l l u 2 两点至少有一点不在托中，不妨 设u 1g 托，设 = ( x ony ( 五) ，五ny ( 五) ，配ny ( 乃) ) ， 如= ( x ony ( t 2 ) ，x 1f 3y ( 死) ，恐ny ( 正) ) ，并设g l = ( u o ，巩，u 2 ) 是 使赋值为1 的顶点数达到