（运筹学与控制论专业论文）两类图的一些极值问题研究.pdf

r e s e a r c ho ns o m ee x t r e m a lp r o b l e m so ft w ot y p e so fg r a p h s an e s i s s u b m i t t e di np a r t i a lf u l f i l l m e n to ft h er e q u i r e m e n t s | o rt h em s d e g r e ei nm a t h e m a t i c s b y y a hl i x i a p o s t g r a d u t ep r o g r a m s c h o o lo fm a t h e m a t i c sa n ds t a t i s t i c s c e n t r a lc h i n an o r m a lu n i v e r s i t y s u p e r v i s o r ：l is h u c h a o a c a d e m i ct i t l e ：p r o f e s s o r s i g n a t u r e ： a p p r o v e d m a y , 2 0 1 1 s 肌c h 叼- i 华中师范大学学位论文原创性声明和使用授权说明 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下，独立进行研究工 作所取得的研究成果除文中已经标明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果对本文的研究做出贡献的个人和集体，均已 在文中以明确方式标明本声明的法律结果由本人承担 作者签名：尝砀霞 日期：知j f 年占月加日 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定，即学校有权 保留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借 阅本人授权华中师范大学可以将本学位论文的全部或部分内容编入有关数据库 进行检索，可以采用影印、缩印或扫描等复制手段保存和汇编本学位论文同意 华中师范大学可以用不同方式在不同媒体上发表、传播学位论文的全部或部分内 容 作者签名：萎砀窿 日期：洲1 年岁月如日 导师签名： 钏； 护 b 凝：如| | 年旯弓日 本人已经认真阅读“c a l i s 高校学位论文全文数据库发布章程”，同意将本人 的学位论文提交“c a l i s 高校学位论文全文数据库”中全文发布，并可按“章程”中 的规定享受相关权益同意论文提交后滞后：口半年：口 1 或q i l ，则 p ( r g ( 札，v i i ，仇1 ) ， ) ) p ( g ) 对于任何图g 和口屹，设厶( g ) 是通过去掉矩阵l ( g ) 中与点口相应的行 和列而得到的主子式 引理2 1 1 ( 4 8 1 ) 设g 是将礼一f 日1 个不同的悬边( 不在日中) 都粘到子图 日( 至少有两个点) 上的某个点u 而得到的n 阶连通图则 妒( g ) = ( z 一1 ) “一1 日i i ，o ( h ) 一( 死一i h i ) z ( x 一1 ) n 1 日i 一1 妒( l 。( 日) ) 6 o箩巳乙蕾各乙蛰、 d 蘸藏 呸$零叭一事霉 硕士擘位论文 m a s r e r st h e s i s 设g ，h 是两个边不交的图，且t y ( g ) ，叫y ( 日) 将图g 中的点u 与日 中的点w 重合连在起，得到一个新图，记作：g u w h ( 见图2 ) vo o g 肿p g 1 哪h 图2 ：图g 删日和g v w h 引理2 1 2 ( 【8 】) 设g ，hk a i , t , - 边m 交的非平凡连通图，且u ， y ( g ) ， w y ( 日) 设x 是图g u w h 的尸e 彻仃向量，其中：甄是对应于点i 的分量如 果l l i i ，则 ( i ) # ( g u w h ) u ( g v w h ) 若等号成立，则有i z u l = 1 l ，且x 与x 7 至少有一 个是图g v w h 的p e r r o n 向量，其中： r ( x 飞= l - - a g i ，v i y ( 日) 叫) ； 戤， 否则 ( i i ) 特别地，若h 是二部图，则等号成立当f l - 4 r 又当x 是使得z 札= = t 日( ) 甄= 0 成立的图g v w h 的p e 册n 向量，当且仅当x 7 是使得 z u = 如= ( ) 孔= 0 成立的图g v w h 的p e 彻n 向量 7 ： 硕士学位论文 m a s t e r st h e s i s 第三节含k 条割边的连通图中函数( g ，q ) 的上、下 界 在这节中，我们将确定n 个顶点且含k 条割边的简单连通图中函数f ( g ，o t ) 在 区间( 一。o ，0 ) u ( 1 ，十。o ) 上的最好上界和区间( o ，1 ) u ( 1 ，+ 。o ) 上的最好下界，并刻 画出相应的极图 对于函数y ( a ，口) ，如果q = 0 ，则f ( g ，0 ) = n ，其中n 是图g 的顶点数；如 果o t = 1 ，则y ( g ，1 ) = 。y ( g ) d ( 口) 。= 2 m ，其中m 是图g 的边数因此，只需 要考虑q ( 0 ，1 ) ，q ( 一o 。，0 ) 及q ( 1 ，+ o 。) 这三种情形 下面介绍本节所需用到的几个图 磷是在完全图一k 的其中一个顶点上连k 个独立点而得到的图； 磁是在圈g 一知的其中一个顶点上连一条悬挂路p k + 1 而得到的图； 磷是在圈g 一南的其中一个顶点上连k 个独立点而得到的图 注4 k o = ，竣一1 即是星图k t ，n 一1 ，g z 一2 岂霹，磁= g = 砩 引理3 1 设u 和口是g 中的两个顶点 l ，v 2 ，n ( v ) m ( 1 3 d c ( u ) ) 且让1 ，地，( u ) n v 】( 1 t d g ( 乱) ) 定义g ，= g 一 o r l ，仇7 2 ，t ，) + 让t ，l ? i v 2 ，t 正) ，g = g - u u l ，u u 2 ，u u d + v m ， u 2 ， r u t ，则 ( i ) 当a ( 一o o ，0 ) u ( 1 ，+ o o ) 时，如果d g m ) d g ( ) ，则f ( g 7 ，q ) f ( e ，q ) i 如果d g ( u ) y ( c ，q ) ( i i ) 当q ( 0 ，1 ) 时，如果d g ( u ) d g ( ) ，则，( g ，q ) f ( g ，q ) ；如果如( 札) 如( 口) ，则f ( g ，a ) f ( g ，a ) 证明：用微分中值定理证明注意到，d g ，( u ) = d v ) + s ，d g ，( ) = d g ( v ) 一8 ， d g ”v ) = d o ( v ) + t ，r i g , ，( 仳) = d g ( u ) 一t 对于所有的点叫y u ， ) ，都有 r i g ( w ) = d c ( w ) = d g , ，( 伽) 因此，由顶点度的幂和( c ，q ) 的定义知， y ( g 7 ，q ) 一，( g ，q )d g ， ) 口一d g ( ) n + d i 口( 乱) 口一d o ( t ) 口 ( d g ) 一s ) a d 0 ( t ，) a + ( d g ( t ) + s ) 。一d o ( 似) q = a s ( 叼 一1 一f 一1 ) ， 一 ( 3 1 ) 8 其中：d a ( v ) 一s f l d g ( v ) 且d g ( t 1 ) r h e t a ( u ) + 8 同理有： ，( g ，q ) 一f ( a ，q ) = d g ，( u ) 口一d g ) 。+ d g ，( u ) 口一d a ( u ) 。 = ( d g ( t ，) + t ) a d g ( t ，) 口+ ( d e ( t ) 一t ) 。一d 0 ( t ) 口 = q ( 嚣一1 一绣一1 ) ， ( 3 2 ) 其中，d g ( u ) 巳 d a ( ) + t 且d g ( u ) 一t i ( c ，a ) ；如果d c ( u ) 啦 0 由式( 3 2 ) 得 f ( c ，口) f ( c ，q ) 当口( 0 ，1 ) 时，如果d a ( u ) 如扣) ，则r l l l 0 由式( 3 1 ) 得，( g ，a ) 0 由式( 3 2 ) 可得f ( c ，口) 1 或0 口 ，( 伊，q ) ； ( i i ) 若q 0 ，则有i ( c ，q ) ，( g ，q ) 证明：容易看出，d g ( 铷) = d g ( u o ) ，d g ( u 1 ) = d g ( u 1 ) ，d g ( v o ) = d g ( o ) ， d g ( 忱) = d g ( u 2 ) ，d g ( 1 ) = d g ( u 1 ) 一2 并且，对所有的点叫：= y ( g ) 【咖，u l ， 如，口l ，t ，2 ) ，都有d c ( 叫) = d g ( ”) 因此，由顶点度的幂和f ( a ，q ) 的定义知， i ( c ，a ) 一，( g 。，q ) = d g ( - ) 口+ d g ( z ) n x e v u t o 让1 ，t ，o ，t 均 9 一 d g c 仇，口+ z 6 v ，u 乏。，如，您，d g c 名，。i u 1 o ，u l ，如，您) j = d g ( 口1 ) a 一( d r ( v 1 ) 一2 ) 口 = 2 q p 一( d a ( v 1 ) 一2 d a ( v 1 ) )( 3 3 ) 注意到如( u 1 ) 3 ，因此1 1 或 0 q f ( a ，q ) ：当q 0 时，有f ( g ，q ) f ( g ，q ) 引理得证 口 引理3 3 设 1 ，i 是由点集y ( 尬七) = v o ，v l ，仇) 组成的星图，嘴是将 甄七中的一个悬点与圈c k 一七上的某个点相连而得到的图 ( i ) 如果q ( 一。o ，0 ) u ( 1 ，+ o o ) ，则，( 磷，q ) ，( w k ，q ) ，等号成立当且仅当 = 0 ，1 j ( i i ) 如果q ( 0 ，1 ) ，则，( 铹k ，q ) ，( 磷k ，q ) ，等号成立当且仅当七= 0 ，1 证明：事实上，当七= 0 ，1 时，有醒= 硼= c k 和砩= 砩，因此，结论成 立当k 2 时，由顶点度的幂和的定义知， ，( g k ，q ) = ( n - - k 一1 ) 2 a + ( 七+ 2 ) 口+ 七，( w k ，q ) = ( n - k - 1 ) 2 。+ 忌。+ 3 口+ k - 1 作差得： ，( k ，q ) 一，( 嘴，q ) = ( 七+ 2 ) a k a + 1 a 一3 口 = ( 七一1 ) a ( f 一1 7 7 f 一1 )( 3 l k + 2 且1 7 7 l 后) ( 3 4 ) = 2 q ( 等一馑一1 ) ，( 七 已 k + 2 且1 啦 f ( c ，a ) ； ( i i ) 如果q ( 一。o ，o ) ，则f ( o + u t ，口) f ( a ，a ) 1 0 证明：令v 7 = y t ，t ， ，由顶点度的幂和的定义可知， f ( a + u u ，q ) 一f ( a ，a ) = d ( 让) a + ( d ( u ) + 1 ) 口+ ( d ) + 1 ) a 一睡绀州h 训口) = q ( p 1 + 矿_ 1 ) ， ( 3 6 ) 其中：d 1 也+ 1 且也 叼 1 及q 1 设 t i ，t k 。且d g ( u ) d g ( t ，) 令( u 7 ) 心】= 叫l ，1 0 2 ，t u 。) 由t 1 7 知 s t 构造： g 7 = g 一 0 叫l ，叫2 ，仳7 伽8 ) + 删l ，u l u 2 ，t 奶) 显然，g ，蝣由引理3 1 ( i ) ，我们有f ( c 7 ，a ) ( a ，q ) ，矛盾因此，1 l = 1 事实3 g 孵 事实3 的证明：用反证法假定g 誊瓣，则一定存在点t i y ( 玩。) 和 u y ( 。) ( 0 i ，歹七，l 歹) 使得“0 e ( g ) ，i ( u ) y ( 玩。) l 2 且 l ( 0 ) y ( k ) l 2 由事实2 知，k 。= “) 且= ) 不失一般性，设 d g ( u ) d g ( 仳，) 令( ) m = 【z l ，勿，忍) 由l ( 0 ) y ( 玩，) i 1 可知， z 1 构造： g 7 = g 一 钍7 2 1 ，t 上7 勿，u 7 盈】+ u z l ，勿，u 魂) ， 则g ，鳅由引理3 1 ( i ) 知，( g ，q ) ( c ，a ) ，矛盾 结合事实2 和3 ，可分别假定= 【u i ( o i 七) 和u o 吩e ( g ) ( 1 j 七) 不失一般性，假设妣o 七一1 口l 1 事实4 g 兰k ( 口o ， 1 ，1 ，佗一a 0 一七+ 1 ) 、_ _ 。- i _ ， 七一l 1 2 事实4 的证明：假定对某一个i ( 1 i k 一1 ) ，有毗 1 ，则a k 1 不失一 般性，设d g ( u 七) d g ( ) 令( 撕) t 0 = 秒l ，耽，一l 构造： g ，= g 一 u , y l ，u i y 2 ，地一1 ) + u k y l ，u k y 2 ，t k 一1 ) ， 则g 7 瞬由引理3 1 ( i ) 可知，f ( c ，口) f ( c ，q ) ，矛盾 事实5 a o = n 一七 事实5 的证明：注意到，a o = n 一( a l + + n 七) n k 用反证法，假 设a o 1 令( u ) 铂 = _ 【玑，y 2 ，y a 。一l 及 ( t o ) ) = z l ，z 2 ，z a o 一1 ，t l ，u 2 ，u k 1 ) 如果d g ( v , o ) d g ( u k ) ，则定义： = g 一 u k y l ，u k y 2 ，t 七弧k 1 ) + u o y l ，u o y 2 ，t o 一1 ) 如果d o ( ) d c ( 伽) ，则定义： g ，= g 一 u o z l ，u o z 2 ，咖一1 ，u o u l ，u o u 2 ，咖让七一1 ) + u k z l ，7 t k z 2 ，u 膏五一1 ，t 正k l t l ，u k u e ，t 七u 七一1 ) 显然，无论哪种情形，都有g 7 鳅由引理3 1 0 ) 知，厂( g 7 ，q ) i ( g ，q ) ，矛盾 综上所述，定理3 5 得证 口 以下考虑q 0 时的情形首先证明下面的断言1 断言1 设g 是图类雠中f ( c ，q ) 值最大的那个图，则当a 0 时，g e l 中的 每一个分支要么是一个圈，要么是一个孤立点 证明：用反证法假设g 一置中存在一个既不是圈也不是一个孤立点的 分支，设为g 1 容易看出，g 】是一个2 连通图选择g 1 中最大的那个圈，记 作q = u l 抛一1 u i + l 让，u 件l u t u l 注意到，g 1 不是团因此，g l 中 一定存在两点，不妨设为讹，t j 以u i ，u ，为端点的路p 与圈g 相交，且满足 v ( p ) ny ( g ) = ，嘞) ( 见图5 ) 下面分两种可能的情形来证明我们的结论 ， 情形1 路p 的长度为1 ；见图5 ( a ) 令g 7 = g 一呦注意到a i ( c ，n ) ，与假 设矛盾 情形2 路p 的长度至少为2 1 3 c ， “l 越，厂t 6 ) ； ： j ，1 义陟q “j 图5 ：g 1 包含p = u i 吩，或p = 讹v l v 2 铆一l v l u j 令p = u i v l v 2 叻一l v l u j ( 见图5 ( b ) ) 当f = 1 时，容易看出，不存在整数 七 i 一1 ，i + 1 ，j 一1 ，歹+ 1 】使得u l u k e ( g ) 否则，g i 一定包含一个长至 少为+ i 的圈，与假设矛盾定义g = g 一【u t 1 ，呦嘶+ 1 + u j + l u l 此种情况 的证明方法与下面f 2 的情形类似，在此略去过程当f 2 时，容易看出， v l y , , i 一1 ，u i u 4 + i ，铆一1 ，仇+ 1 譬e 定义： g ，= g 一 地一1 ，嘶+ l ，叻一l 饥) + 仇吻+ 1 ，协一l 地一1 ) 注意到，如，他) = d g ( u t ) 一1 ，d g ，( 嘶) = d g ( u j ) 一1 ，且对于所有的点伽 y 啦，) ，都有d g ，( 伽) = d e ( w ) 由顶点度的幂和的定义知， ，( g ，q ) 一f ( g ，0 1 ) = d a ，( 地) 口一d c ( 地) a + ( d a ，( 嘶) a d c ( 嘶) ) = ( d g ( t k ) 一1 ) a d g ( t “) a + ( d c ( u j ) 一1 ) 。一d g ( u j ) a = 一q ( 毒。一1 + 矿一1 ) ， 其中，d g ) 一1 d a ( u t ) 且d a c , , j ) 一1 叼 f ( a ，a ) ，矛盾 断言i 得证 口 定理3 6 当a 0 时，在所有含n 个点k 条割边的连通图中，磷( 见p 占中 的描述) 取得最大的f ( c ，q ) 一值 证明：只需证明当口 i ( g ，q ) ，矛盾因此，g 恰好包含一个圈 由g 有k 条割边可知，g 中包含的圈的圈长为n k 断言3 g 皇c 2 断言3 的证明：由断言2 可知，g 恰好包含一个圈，不妨设为c 用反证法， 假设g 喾诺选择g 中的最大度点，不妨设为z 若存在一个与点z 不相邻的悬点t ，设其邻点为t ，定义g ，= g 一让t ，+ 讹注 意到，始，( z ) = d c 仕) + 1 ，d g , ( v ) = d c ( t ，) 一1 ，且对于所有的点w y z ，口) ，都有 d g ，) = d v ( 叫) 因此， ，( g ，a ) 一i ( e ，q ) = d i ( z ) a d 0 ( z ) 口+ ( d g ， ) n d v 扣) a ) = ( d g ( x ) + 1 ) 口一d g ( z ) 口+ ( d g ( u ) 一1 ) a d a ( v ) 口 = q ( p 一矿- 1 ) ，( 3 7 ) 其中：d g ( z ) d g 仕) + 1 且d g ( ) 一1 7 7 d g ( 可) 容易看出，如( u ) 如0 ) = ( g ) 因此，7 7 ，( u 2 ，q ) ，矛盾否则，令 n ( x ) = 扣l ，耽，仇，订，其中，d ( v i ) = 1 ( i = l ，2 ，t ) 且d ( y ) = 2 定义： g = g 一 z 可1 ，t , v 2 ，x v t + y v l ，y v 2 ，y v t 容易看出，d a , ( z ) = 1 ，d c ，( y ) = t + 2 ，且对于所有的点w y 扛，可) ，都有 d g ，) = d a ( ) 注意到，t + 1 4 因此， ，( g 7 ，0 1 ) 一i ( g ，q ) = d g ，( y ) 。一d g ( 可) 。+ ( d g ，( z ) a d g ( z ) a ) = ( t + 2 ) 。一2 a + 1 a 一( t + 。1 ) 。 = ( ( + 2 ) 。一( t + 1 ) 口) 一( 2 。一1 a ) = q ( p 一一矿1 ) ，( 3 8 ) 其中：- 1 叩 2 t + l 1 和o 1 时有f ( g ，o t ) f ( c ，a ) ，矛盾因 此，g 恰好包含一个圈 由g 有k 条割边可知，g 中包含的圈的圈长为n k 事实3 7 g 笋磺。 事实3 7 的证明：由引理3 1 ( i ) 知，圈c k 一七上恰好粘有一个悬挂树，不妨设 为t ，粘点为锄假定树t 不是一条路选择以坳为起点的最长的一条路，显然， 其终点是一个悬点，设为u 1 定义路p ：= u o u l f ( 1 z 七) ，则由我们对t 的 假设，p 上一定存在一个点讹，使得d g ( ) 3 ，或者u i = b 0 且d g ( 让t ) 4 选 择珏：n c ( u d v ( pug 一) 并构造图g ，= g u i u ：+ u z u ：容易验证，g ，璐 注意到，d g ，( t l t ) = d a ( 吨) 一1 ，d g ，( u z ) = 2 ，d a ( u f ) = 1 另外，对于所有的点 w y ，铆) 都有，d a , ( w ) = d a ( w ) 由顶点度的幂和的定义可知， ，( g 7 ，o t ) 一f ( a ，a ) = d g ，( 啦) n d c ( 地) 。+ ( c f g ，( t f ) 口一d g ( u z ) 口) = ( d c ( 啦) 一1 ) 口一d a ( 地) 口+ 2 a 一1 a 1 6 ： 硕士学位论文 m a s t e r st h e s i s = q ( 矿一a - 1 ) ，( 3 9 ) 其中：l ，7 2 d a ( u i ) 一l f d a ( t i ) ，( g ，q ) 1 ，根据等式( 3 9 ) ，有 口 定理3 8 当0 q 1 时，在所有含n 个点七务割边的连通图中，c ：取得 最小的f ( a ，q ) 值 ，证明：只需证明当0 q 1 时，如果g 瞬，则f ( a ，q ) ，( 嘴k ，n ) ，等 号成立当且仅当g 兰磁 当七= 0 时，由事实1 7 知，g = c k ，定理成立因此，只需要假定k 1 为 了完成定理3 8 的证明，我们将证明下列断言 断言1 7 g 恰好包含一个圈长为n k 的圈 断言1 的证明：由事实1 7 知，g e l 要么是圈，要么是孤立点如果g 恰好 包含一个圈，则结论成立因此，可假设g 包含至少两个圈，则由引理3 2 ( i ) 知， 一定存在一个连通图g 鳓，使得当0 a 1 时有f ( a ，q ) f ( a ，q ) ，矛盾 因此，g 恰好包含一个圈 由g 有k 条割边可知，g 中包含的圈的圈长为n 一七 断言2 7 g 垒c 尝 断言2 的证明：由断言1 可知，g 恰好包含一个圈，不妨设为c 用反证法， 假设g 碧畿选择g 中的最大度点，不妨设为z 若存在一个与点z 不相邻的悬点u ，设其邻点为t ，定义g 7 = g 一删+ t , b 注 意到，d a , ( x ) = d a ( z ) + 1 ，d g , ( v ) = d a ( t j ) 一1 对于所有的点叫y 【z ，u ) ，都有 d g ，) = d a ( 叫) 因此， 厂( g ，o t ) 一f ( a ，q ) = d g ，( z ) 口一奶( z ) 。+ ( d g ， ) 。一如( u ) 。) = ( d a ( z ) + 1 ) a d 0 0 ) n + ( d 0 ( 口) 一1 ) a d g ( v ) 口 = = 口( 口一1 一o c - 1 ) ，( 3 1 0 ) 其中：d a ( x ) r i g ( = ) + 1 且d a ( v ) 一1 7 7 d g ( v ) 容易看出，d v ( v ) d v ( x ) = ( g ) ，因此，f 7 f 由等式( 3 1 0 ) 2 乏0 q 1 知，( a ，a ) ，( g ，q ) ， 矛盾 1 7 若g 中所有的悬点都与点z 相邻，则g 要么同构于嘴( 定义于引理3 3 中) ， 要么可通过由一条内部路r - - t + l 将星图硷t 的中心与圈g 一詹上的某一点连接 起来而得到这里，一t + 1 3 且t + 1 4 容易看出，七5 当g 垒嘴 时，由于k 5 ，根据引理3 3 ( i i ) ，我们有，( 磷，o t ) 厂( 嘴，q ) ，矛盾否则，令 ( z ) = 口l ，7 1 2 ，仇，s ， ，其中，d 以) = t ( i = 1 ，2 ，t ) 且d ( y ) = 2 构造： g ，= g 一 x v l ，x v 2 ，x v t + ( y v l ，y v 2 ，y v t 容易验证，d a , ( z ) = l ，d a ( y ) = t + 2 ，且对于所有的点w y z ，秒 ，都有 d g ，( 伽) = d a ( ) 注意到，+ 1 4 因此， ，( g ，o t ) 一f ( c ，o t ) = d a ，( 可) 。一d g ( ! ，) 。+ ( d g ，( z ) 盘一d g ( z ) a ) = + 2 ) 口一2 a + 1 a 一0 + 1 ) 口 = ( ( + 2 ) 。一0 + 1 ) 。) 一( 2 。一1 口) = a ( p 一，? a - i ) ，( 3 1 1 ) 其中：1 f 7 2 t + 1 t + 2 f ( g ，q ) ，矛盾因此，g 垒磷 根据断言2 ，定理3 8 得证 3 3 总结论及其证明 通过直接计算，有。 由等式( 3 1 1 ) 及0 q 1 ，则 ， ( n 一2 ) 2 a + 3 n + 1 f ( c ，o t ) ( 仃一k 1 ) a + 1 + ( n 1 ) e + 乜 左边等号成立当且仅当g 竺p 2 ，右边等号成立当且仅当g 皇磁 1 8 由定理3 6 ( 4 2 ) 可得，当q 0 ( o q 1 ) mn 个顶点k 条割边的图类中函数 f ( g ，q ) 的上界( 下界) 定理3 1 0 令g 鳓 ( i ) 若q 0 ，则 f ( g ，q ) ( n k 一1 ) 2 a + ( 七+ 2 ) a + k ， 等号成立当且仅当g 皇磷 ( i i ) 若0 q 1 ，则 f ( g ，q ) ( n k 一1 ) 2 a + ( k + 2 ) a + 詹， 等号成立当且仅当g 望磷j 注5 本节的结果已被国际s 凹刊物g r a p h sa n dc o m b i n a t o r i c s 录用( g r a p h s a n dc o m b i n a t o r i c s ( 2 0 1 0 ) ，d o h1 0 1 0 0 7 s 0 0 3 7 3 0 1 0 0 9 9 6 - 8 ) 第四节给定围长的三圈图的l a p l a c e 谱半径的上界 本节将给出在图类。绍中恰好包含三个圈( 四个圈) 的l a p l a c e 谱半径最大的那 个三圈图另外，也确定了当g 为偶数时图类刃中三圈图的l a p l a c e 谱半径g j = 界及相应的极图 由g e n g 和l i 【1 0 ，3 3 】易知，一个三圈图包含至少三个圈，至多七个圈，且不 可能包含五个圈定义三圈子图类： 。绍= g ：g 是刃中恰好有t 个圈的三圈图，其中i = 3 ，4 ，6 ，7 ) 定义磋 ，磋。，脚，磁。r l 为图6 中所示图形 凳 图6 ：三圈图磁 ，罐口一。和罐q ，矿 为了得到结论，先证明下列引理 图7 ：通过一条路将殆和星图虬知连接起来得到图g 引理4 1 设g 为图类刃，3 ( 钾一，霸，6u 。绍7 ) 中l a p l a c e 谱半径最大的 图，则9 是通过将所有的悬挂边( 如果存在的话) 都粘在t c 上的同一个点而得 到的 7 器 u 6 器 u 4 邪 u 3 刃 = 刃 拣显 证明：设x = 0 l ，z 2 ，z n ) t 为g 。的p e r r o n 向量 首先，我们断言伊的所有悬点都只有一个共同的邻点否则，令嵋，吗为 9 两个不同的点，且它们分别为悬点u l ，t 2 的邻点由于口是极图，根据引理 2 1 1 ，有：= z u o = 0 和l = x u , j = 0 设u 3 为g 中某一个点且z u 3 0 ，则 i z “l l z t l 3 i 根据引理2 1 1 ，我们有u ( g ) u ( g 一t l 嵋+ t 1 u 3 ) ，矛盾 上述断言意味着伊是一个由一条路将中的某一点t ，与星图k l , k 的中心 t ，相连接而得到的图( 见图7 ) 下面只需证明u = 用反证法，假设t ，t ，如果 i i i z 。小则由引理2 1 1 ，p ( 9 ) 肛( g ，) ，其中： g = g 一uv v i + u t ，仇 q ( 管)v i e n t g 扣) 矛盾因此有i i l 甜i 根据引理2 1 1 ，p ( 口) p ( g ，) ，其中： g = g + 一 t l t ，7 ，u 2 1 ，t 詹t ，) + u l u ，锄t ，u k v 由g + 是极图且k 1 七为二部图可知，u ( c + ) = u ( g ) 因而= z t ，= 0 令t l ， 为g 中某一个使得z 埘0 的点，则i z t ，i i z 埘| 根据引理2 1 1 ，有p ( 伊) l l ，定义： g = g 一 1 3 1 j 1 ，v v 2 + w v , ，w v 2 ， 则g ，霸，v 根据引理2 1 1 ，p ( g ) p ( g ，) ，矛盾因此有i z 脚l i | 设点w 的邻点集为 u l ，u 2 ，u 七】：定义： g = g + 一【”u l ，叫t 正2 ，叫t 正詹】+ 牡l ，u u 2 ，t ，u 七) ， 则g 刃3 由引理2 1 1 知，p ( 口) p ( g ) 注意到，9 是图类。绍3 中 l a p l a c e 谱半径最大的图因此，p ( 口) = p ( g ”) 另一方面，g 中的悬挂星图 是一个二部图，因而有i i = l z 叫i = 0 设u 为9 中使得0 的一个点，则 l = i l l z u | 定义： 0 = g 一 叫t 正l ，伽t 正2 ，叫乱奄) + u u l ，u t 正2 ，t 仳七) ” 则g 肿卯，v 由引理2 1 1 可知，p ( 9 ) p ( g 胛) ，矛盾因而，w v 其次证明l 矿i = 1 假设l 矿i 2 ，则一定存在一个点t ，矿使得口叫同理 可证，一定存在一个图g 。绍，3 ，使得p ( 口) p ( g ) ，矛盾 ， 因此，在这种情形中，亦可以得到对于某个p ，q g ，有g + 垒硫乒埘q - 2 ) 成立 综合晴形1 和情形2 ，引理4 2 得证 口 ： 硕士学住论文 m a s t e r st h e s i s 定理4 3 设g 是图类卯3 中l a p l a c e 谱半径最大的那个图，其中佗3 9 2 ， j , jg 垡玩笋+ 2 且u ( c ) n 一3 9 + 9 + 茅丽6 证明： 根据引理4 1 ，对于某个p ，q g ，有g + 竺瑞埘9 2 ) 用反证法 假设p g + i ，则n 3 9 1 方便起见，令七= n 一( 9 + p + q 一2 ) 为g + 中悬挂 边的数目因此，k n 一3 9 + 1 注意到，g 不可能为正则图或者半正则图，由 引理2 8 ( i i i ) 有： 胛) m a x d + m i | 眯v ( c = 七+ 6 + 等= 七十7 + 雨6 容易验证，k + 7 + 丽6 关于非负数后递增结合几3 9 1 ，我们有 。 r p ( 9 ) p ( g ) ，矛盾因此，p = 9 同理可证，g = g 因此，g 垒虢泸帕又玩笋+ 2 既不是正则图也不是半正 则图，因而 p ( 臻- ，9 3 9 + 2 ) m a x r i d + m l v i y ( 互怎挈+ 2 ) ) = n 一3 9 + 9 + n - 3 l 9 一+ 8 - 定理证毕口 4 2 三圈子图类刃，4 中l a p l a c e 谱半径的上界及相应极图 定义口p ，q ，) 是一个由三条两两不相交的内部路p 舛l ，b + 1 ，b + 1 通过交于相 同的端点而组成的良图对于任意图g 韶，4 ，其基图殇即是类型正，这里 t 8 ，9 ，1 0 ，1 1 ( 见图1 ) 令a 为一个圈，其中8 g 设最= t 1 u 2 u l 为连接 口0 ，g ，r ) 和g 的一条路，其中：u 1 y ( 口，口，r ) ) 且锄y ( g ) 如果z = 1 ，则殆即为类型噩或码否则，即是类型正。或者丑1 引理4 4 设g 是图类刃，4 中l a p l a c e 谱半径最大的那个图，则g 。髦 t o 掣1 u s ，其中：只可能是类型t s 或乃，u l 是殆。中的最大度点且u 是星图 s 的中心 证明： 由引理4 1 可知，g 型u v s ，也就是说，g 是通过在死上的某 一点u 上粘上星图s 的中心t ，而得到的图方便起见，令l y ( s ) i = kf + 1 ，其中七 是图9 悬点的数目易知，k 0 2 3 ：一， 硕士学位论丈 m a s t e r st h e s i s 如果t g 是类型正。或五l ，则由引理2 8 ( i i i ) 可得，当k 0 时，有 邸) 老“ - - ：y n ，由l 2 知， p ( 磅口+ r i - 。1 ，、+ 1 = k + l + 5 k + 7 因此，u ( a ) l z u 。i ，则根据引理2 1 1 ，有 u ( g 。) u ( c , u , u ( g 。一y ( a t 1 1 ) ) ) ， 矛盾因此，l z u l l ，i 由引理2 1 1 可知，u ( a ) p ( 殆u l v s ) 又g + 为极图 且星图s 是二部图，因而u ( a + ) = p ( u l v s ) 且钆= z ，= 0