（应用数学专业论文）extremal+problems+on+general+randic+index.pdf

摘要 r a n d i d 指标是一种十分重要的化学拓扑指标，它与有机物的结构和性质有 着非常紧密的关系它最初由美国著名化学家m i l a n r a n d i d 于1 9 7 5 提出，以后 许多化学家和数学家都加入了对该指标的研究行列，并得到了很多有价值的 结果。 由于化学家总想试图探求物质的分子机构与r a n d i d 指标值的关系，即什 么样的分子结构有大的r a n d i 6 指标值，什么样的分子结构有小的r a n d i d 指标 值，以此来帮助他们建立资料库便于合成新的物质，故极值问题成为r a n d i d 指 标研究中的一个有趣和有应用背景的研究分支，同时我们可以很容易看出它 本身也是极值图论的一个典型的应用在本文中将主要讨论了两类极值问题： 对一般图的广义r a n d i d 指标的极值问题和对于化学图的r a n d i c 指标r i 的极 值问题另外我还给出了一个关于r a n d i d 指标的猜想的部分证明，在本文的 最后还指出了其它几个研究者很感兴趣的r a n d i 6 指标研究课题。 本文在定理证明中运用了多种不同的方法，如归纳法，基本不等式，代数 变形，和经典图论方法 关键字：r a n d i 6 指标，广义r a n d i d 指标，化学树，弱正则图 e x t r e m a lp r o b l e m so i lg e n e r a lr a n d i di n d e x y i t i n gy a n g a b s t r a c t r a n d i di n d e xi sak i n do fi m p o r t a n tc h e m i c a lt o p o l o g i c a li n d i c e sa n di sc l o s e l yc o n n e c t e dw i t ho r g a n i cm a t t e r ss t u r c t r u ea n d q u a l i t i e s i tw a sf i r s tp r o s e db ym i l a nr a n d i d ，a f a m o u sa m e r i c a nc h e m i s t r e s e a r c ha b o u ti th a sb e e ne x t e n s i v e l yd e v e l o p e da m o n g m a n y c h e m i s t sa n dm a t h e m a t i c i a n sa n dm a n yv a l u a b l er e s u l t sa r ea c h i e v e d s i n c ec h e m i s t sw a n tt ok n o wt h er e l a t i o n sb e t w e e nm o l e c u l es t r u c t u r ea n dr a n d i d i n d e x ，i ew h a tk i n do fm o l e c u l a rh a v et h el a r g e ro rs m a l l e rr a n d i di n d e x ，e x t r e m a lp r o b l e m b e c o m ea ni n t e r e s t i n ga n du s e f u lb r a n c ho ft h er e s e a r c ho nr a n d i 6i n d e x ，w h i c hi sc l e a r l ya a p p l i e db r a n c ho fe x t r e m a lg r a p ht h e o r yt o o i nt h i sp a p e r w e m a i n l y d i s c u s st h ef o l l o w i n g t w oe x t r e m a lp r o b l e m s ：t h ee x t r e m u mf o rg e n e r a lr a n d i di n d e xo fg e n e r a lg r a p h sa n d t h ee x t r e m u mf o rr a n d i di n d e xr io fc h e m i c a lf l e e s a d d i t i o n a l l y ，ap a r t i a lp r o o fo fa c o n j e c t u r eo nr a n d i di n d e xi sg i v e n s i n c et h er e s e a r c ho nt o p o l o g i c a li n d i c e sn e x 。e rl i m i t s t ot h er e s e a r c ho fe x t r e m a ip r o b l e m ，m a n yo t h e rr e s e a r c hp r o b l e m sa r ep r e s e n t e di nt h ef i n a l p a r to f t h i sp a p e r i nt h i sp a p e rip r o v et h et h e o r e m sb yaf e wd i f f e r e n tw a y s s u c ha si n d u c t i o n ，b a s i c i n e q u a l i t y ，a l g e b r at r a n s f o r m a t i o na n d c l a s s i cg r a p h t h e o r yw a y s k e y w o r d s ：r a n d i d i n d e x ，g e n e r a lr a n d i di n d e x ，c h e m i c a lt r e e ，w e a k l yr e g u l a rg r a p h e x t r e m a lp r o b l e m so r lg e n e r a lr a n d i di n d e x y i t i n gy a n g 0 i n t r o d u c t i o n i ti sk n o w nt oa l lt h a tak i n do f m a t t e r sc h e m i c a la n dp h y s i c a iq u - , f l i t i e sa r ec l o s e l yc o n n e c t e dw i t hi t sm o l e c u l a rs t r u c t u r e s om o l e c u l a r g r a p hw h i c h s h o wi t ss t r u c t u r ea r ew i d e l y u s e d - nt h er e s e a r c h b u tf o rc o n v e n i e n c e i nt h er e s e a r c ho f o r g a n i cm a t t e rc h e m i s t sa n d m a t h e m a t i c i a n ss i m p l i f i e dt h em o l e c u l a r g r a p hb yr e p l a c i n gc h a r c o a la t o m sb y av e r t e xa n d o m i t t i n gt h eh y d r o g e n o u sa t o m sw h i c hi sc a l l e dc h e m i c a lg r a p h ( s e ef i g u r e1 ) u n d e rt h i s s i m p l i f i c a t i o n ，r e s e a r c h e r sp r e s e n tt h et o p o l o g i c a li n d i c e sw h i c hp r o v e dt ob ev e r yh e l p f u l f 。ft h er e s e a r c h i n1 9 4 7h a r o l dw i e n e r p r e s e n t e dt h ef i r s tt o p o l o g i c a li n d e xw i e n e ri n d e x 1 0 ，3 9 】d u r i n gh i sr e s e a r c ho na c y c l i cm o l e c u l e s w i t l lt h ed e v e l o p m e n to fm o l e c u l a r c h e m i s t r y , m o r ea n d m o r e t o p o l o g i c a li n d i c e sw e r ep u tf o r w a r d a n dl o t so fv a l u a b l er e s u l t s w e r ea c h i e v e d i n1 9 7 5t h ep u b l i c a t i o no fr a n d i 6 sp a p e ff 3 4 1s e tt h es t a g ef o rah o v e lr e p r e s e n t a t i o n o fm o l e c u l a rs t r u c t u r e i n 内ep a p e rm i l a nr a n d i dd e s c r i b e das k e l e t a lb r a n c h i n gi n d e x t h a tc o r r e l a t e dw i t ht w op h y s i c a lp r o p e r t i e so fa l k a n e s ( s e et h ef o l l o w i n gf o r m ) k i e ra n d c o w o r k e r ss h o w e dt h a tt h eb r a n c h i n gf o r m a l i s mc o u l db e a p p l i e dt os t r u c t u r e so t h e rt h a n a t k a n e sf 1 8 2 稚t h e b r a n c h i n gi n d e xw a s r e n a n l e dt h em o l e c u l a rc o n n e c t i v i t yi n d e xf 2 8 l a n do f t e nr e f e r r e dt oa sr a n d i 6i n d e x a f t e r w a r d si tw a s w i d e l ya p p l i e di no r g a n i cc h e m 。 i s t r y ，m e d i c i n a lc h e m i s t r ya n dp h a r m a c o l o g y 瑟7 c o u n t l e s sp a p e r sa n dt w ob o o k sh a v e b e e nd e v o t e dt or a n d i di n d e xa n di t sv a r i o u sg e n e r a l i z a t i o n s n o to n t yc h e m i s t sb u ta l s om a t h e m a t i c i a n sa r ei n t e r e s t e di ni t af e we a r l yr e s u l t s r e s e a r c ho nm a t h e m a t i c a lp r o p e r t i e so fr a n d i di n d e xw a ss t i m u l a t e db yas e r i e so fp a p e r s d e s c r i b i n gc o r i j e c t u r e so b t a i n e dw i t ht h ea u t o m a t e ds y s t e m g r a f f i t i o r a f f i t ib u i l d sc o b ， j e c t u r e sa b o u tt h er e l a t i o na m o n g r a n d i 6i n d e x ，m a t c h i n g ，i n d e p e n d e n c ea n ds oo n m o r e t h a nad o z e nc o n j e c t u r e so fg r a f f i t io nr a n d i 6i n d e xr e m a i no p e n ( 7 ，l 3 】d e s p i t et h i sa c t i v i t y , s o m ef u n d a m e n t a lq u e s t i o n sr e l a t e dd i r e c t l yt or a n d i i r i d e xa r ey e ts o m e w h a tu n t o u c h e d ，i np a r t i c u l a rc o n c e r n i n ge x t r e m a lg r a p h su n t i lb o l l o b 酝a n de r d 6 s sp a p e r 【3 】w a s p u b l i s h e d f o ra g r a p hg = ( e 嚣) + w e d e n o t et h en u m b e ro f r e i c e s ( o r d e r ) b yna n dt h en u m b e r o f e d g e s ( s i z e ) b ym ，a n df 碲a n yv e r t e xv v w e d e n o t ei t sd e g r e eb y 联v ) l e tgb ea g r a p hw i t ht h ev e r t e xs e tv ( o ) a n dt h ee d 钟s e te ( g ) t h er a n d i di n d e xi sd e f i n e da s r ( 回= 、丽丽1 u v e e ( gv 1“，“、” h e r ew ec a ne a s i l ys e et h a ti s o l a t e dv e r t i c e sc o n t r i b u t ez e r ot or ( o ) s ow e o n l ys t u d y t h e g r a p hw i t h o u ti s o l a t e dv e r t i c e s m a t h e m a t i c i a n sg e n e r a l i z e dr a n d i i n d e xb yr e p l a c i n g ”i 百丽i ”a b 。v e b y ( 菇( f ) d ( v ) ) 8w h e r ea i sar e a ln u m b e r a n dc a l l e di tg g ，i p r a lr a n d i d 抽j “， e x t r e m a lp r o b l e m so ng e n e r a lr a n d i di n d e x y i t i n gy a n g c h 3 c 矿一c 日一c h 3 _ r r il ll c h 3c h 3 f i g u r e1 ：m o l e c u l a rg r a p ha n d c h e m i c a lg r a p h i nt h i sp a p e r1w i l lm a i n l yd i s c u s st w oe x t r e m a lp r o b l e m so ng e n e r a lr a n d i di n d e x b e f o r ed i s c u s st h e m ，l e t sk n o ws o m eb a s i cd e f t n i t i o n sa n dn o t e s f o rar e a ln u m b e r a ，w eu s el a jt od e n o t et h em a x i m u mi n t e g e rs m a l l e rt h a no re q u a lt o n ，a n df a lt od e n o t et h em i n i m u mi n t e g e rg r e a t e rt h a no re q u a lt oa w ec a l lat r e ea nr - s t a r i fi ti sas t a rw i t hr ( r2 1 ) l e a v e s a1 - s t a ri ss i m p l y c a l l e das t u bw ed e n o t et h em i n i m a l d e g r e eb y6a n d t h em a x i m a l d e g r e eb y t h eu n i q u eg r a p hw h i c h a r i s ef r o mac o m p l e t e b i p a r t i t eg r a p hk 5 一6b yj o i n i n ge a c hp a i ro fv e r t i c e si nt h ep a r tw i t h6 v e r t i c e sb yan e w e d g ei sd e n o t e db yk ；月矗ag r a p h i sc a l l e daw e a k l yr e g u l a r g r a p hi ft h e r ea r et w o k i n do f d e g r e e si nt h eg r a p h l e t “vb ea ne d g eo fag r a p hg w e d e n o t et h eg r a p hb yd e l e t i n gt h e e d g e “vb y g u v h e x a n ei s o m e r sr a n d i 6i n d e xb o i l i n zp o i n th e a to ff o r m a t i o n 2 9 1 4 6 8 7 ( 1 )3 9 9 6 ( 5 ) i 2 8 0 8 6 3 2 ( 2 )4 1 0 2 ( 4 ) f 2 7 7 0 6 0 3 ( 3 )4 1 6 6 ( 2 ) 1f 一 2 6 4 3 5 8 0 ( 4 )4 2 4 9 ( 3 ) i 2 5 6 1 4 9 7 ( 5 )4 4 3 5 ( 1 ) 1 f o r m ：r e l a t i o no fp r o p e r t i e st os t r u c t u r ea n dr a n d i ei n d e xf o rh e x a n ei s o m e r s 2 呈! ! 璺竺! ! ! ! ! ! ! ! 竺! ! ! ! ! ! ! ! 型垦竺! 笙! ! ! ! !一j 兰三坚! j ! ! 坚 1 s h a r pb o u n d s f o rt h eg e n e r a lr a n d i di n d e x i nt h i ss e c t i o nw eo b t a i nt h el o w e ra n du p p e rb o u n d sf o rt h eg e n e r a lr a n d i 6i n d e xa m o n gg r a p h s w i t h ，lv e r t i c e sa n dc h a r a c t e r i z et h eg r a p h sw h o s eg e n e r a lr a n d i di n d i c e sr e a c ht h em a x i m u m a n d m i n i m u m w e g i v eac l e a rp i c t u r ed e p e n d i n g o nt h er e a ln u m b e rai nd i f f e r e n ti n t e r v a l s 1 1 b a c k g r o u n do f t h er e s e a r c ho n r a n d i di n d e x b o l l o b , 5 sa n de r d 6 s 【3 】g a v eas h a r pl o w e rb o u n df o rt h er a n d i 6i n d e xo fg e n e r a lg r a p hw i t h nv e r t i c e s t w oy e a r sl a t e r , f a j t l o w i c z 【5 】g a v eas h a r pu p p e rb o u n df o rt h er a n d i di n d e xo f g e n e r a lg r a p hw i t h nv e r t i c e s b o l l o n t sa n de r d 6 sa l s og e n e r a l i z e dt h er a n d i di n d e x ，a n d s t u d i e dt h ee x t r e m a lp r o b l e mo fg e n e r a lg r a p hw i t hm e d g e s t h e f o l l o w i n gt h e o r e m sa r et h em a i n k n o w nr e s u l t ss of a ro nt h el o w e ra n du p p e rb o u n d s f o rt h er a n d i di n d e xa n d g e n e r a lr a n d i 6i n d e x t h e o r e m1 1 1 3 1l e tgb eag r a p ho f o r d e rn ，c o n t a i n i n gn oi s o l a t e dv e r t e x t h e n w i t he q u a l i t yi f a n do n l yf i gi sas t a r r ( o ) 厢 t h e o r e m1 2 e 5 。t h e o r e m1 1a m o n g g r a p h sw i t hnv e r t i c e s , t h eg r a p h sw i t h o u t i s o l a t e d v e r t i c e s , i nw h i c ha l lc o m p o n e n t sa r er e g u l a r , h a v et h em a x i m u mr a n d i di n d e x , e q u a lt o n 2 t h e o r e m1 3 1 3 1e v e r yg r a p hg o f s i z ems a t i s f i e st h a t ，d r 0 0 t h i si sav e r ys i m p l ec a s e s i n c ei ti se a s yt os t h a ta d d i n ge d g e st oag r a p hw i l l i n c r e a s et h es u m ，w h i l ed e l e t i n ge d g e sw i l ld e c r e a s et h es u m s o ，w e g e t ar e s u l tj u s tl i k e t h e c a s ef o r 程一0 t h e o r e m1 8 l e tgb ea g r a p ho f o r d e r c o n t a i n i n gn o i s o l a t e dv e r t e x w h e n 啦 0 w e h a v e ；曼r a ( g ) 曼n _ ( n - - 1 ) 2 a + l f o r ne v e n ，a n d 旱十2 s 粕( 6 ) s 下n ( n - t ) 2 a + l 砖n o d d , w i t hr i g h te q u a l i t yg a n do n l y 簪gi s8c o m p l e t eg r a p h , 蕊w i t h 霹e q u a l i t yi f a n d o n l y 矿g i sa y o r e s t c o m p o s e d 矿s t u b s y o r ne v e n ，a n d a f o r e s tc o m p o s e do f 丁n - 3s t u b s a n da2 - s t a r f o rho d d c a s e i i 一 0 【 0 t h e o r e m1 9 l e tgb eag r a p h o r d e r n ，c o n t a i n i n gn oi s o l a t e dv e r t e x w h e n 一 a n - - z3 + 2 5 ”，如一1 ) 4 十4 t h ef o l l o w i n gt w ol e m m a sw i l lb eu s e di nt h ep m o f l e m m a i t 0 , l e t “￥b e l e a f o f a g r a p hg w h e n 一 镬 筑淞h a v e r “( g ) 一r 。( d 一“v ) 一1 ) 1 + “如一2 ) 1 + 。 p r o o f l e t d ( u ) * 1 ，i f d ( v ) = 1 ，t h e n 露q ( g ) - r a ( g 一“v ) = 1 ( h 一1 ) 1 + 8 一研一2 ) 1 + 4 t h e r e f o r e ，w em a ya s s u m et h a td ( v ) 惫2 。d e n o t eb yr t h es u mo ft h ew e i g h t so ft h ee d g e s ， o t h e r 虫黜t 嚣p 。i n c i d e 攫w i t h 晒v e i t e x 轧t h e n r m ( g ) 一如( g - u v ) = d ( v ) “十s ( 1 一掣) s i n c es 墨( d ( v ) 1 ) d f f ) 。，w eh a v e 基 e x t r e m a ，l p r o 。b 1 e m s o n g e 。n e r a 1 。r ，a n d i 6 i n d ，e ，x y i - t i n gy a n g r 。( g ) 一r 。( g - - u v ) d ( v ) “+ 婶( v ) 一，) d ( v ) “( - 一i 生告苦孓竽) = d ( v ) 1 + 。一( d ( v ) 一1 ) 1 + “ 一1 ) 1 + 4 一一2 ) 1 + 。 _ l e m m a1 1 1 l e tu vb e e d g eo f m a x i m u mw e i g h ti nag r a p hg w h e n 一 a 0 1 ) ) - n o ww et u r nt ot h ep r o o fo fo u rt h e o r e mb ya p p l y i n gi n d u c t i o no nn + f r o m l e m m a 111w ec a nd e l e t et h ee d g e sw i t hm a x i m u mw e i g h t si nag r a p hu n t i la l lo ft h e ma r el e a v e s - s ow ec a na s s u m et h a tt h em a x i m u mw e i g h te d g e si ng a r el e a v e s l e tu 1 ，b eo n eo fs u c h 7 e x t r e m a 1 p ，r o b l e m 。s ，o ，n ，g e n e r a l r a n d i 6 i n d e x y i - t i n gy a n g l e a v e s i fgc o n t m n sn os t u b s ，t h e ng u vh a so n l yo n ei s o l a t e dv e r t e x w ea s s u m et h a tf o r s m a l l e rv a l u e so f n + mt h ei n e q u a l i t y 如( g ) 0 一1 ) 1 “h o l d s t h e n r 。( g ) r a ( g 一“v ) + 0 一1 ) 1 + 。一扣- 2 ) 1 + 。一1 ) 1 + 8 w ec a ns e e t h a to n l y i f g i sas t a r t h ev a l u eo f r f o r 一 a 0 i se q u a l t o s i n c et h ee q u a l i t yh o l d si nt h ei n e q u a l i t yo f l e m m a 1 ，1 0o n l yi f d ( v ) = 1 i fgc o n t a i n sks t u b s ，f r o mt h ea b o v er e s u l tw e h a v et h a t 尺a ( g ) 女十( n 一2 k 1 ) 1 + “ w i t he q u a l i t yi fa n do n l yi fg i sag r a p hc o m p o s e do fks t u b sa n dam 一2 k 1 ) + s t a r w ed e n o t e + 一2 k 一1 ) 1 “b yq 。( 女) s ow eo n l yn e e dt od e t e r m i n em i n q n ( ) 一k = 0 ，1 ，2 ，l 譬j w h e n1 十n 一3 ) 1 + 。n 一1 ) 1 + 4 ，s i n c et h ef u n c t i o n ，( 工) = 工1 + “一扛一2 ) 1 + 8f o r 一 g ( 1 罕j ) s o ，w eh a v e t h a t m i n q 。( 女) ，k = 0 ，l ，2 ，l 孚j ) = 岛n - 一2 j ) w h e n1 + 一3 ) 1 + 8 _ 一1 ) 1 + “，w e d i s t i n c tt h ef o l l o w i n gt w oc a s e s ： 1 i f t h e r ee x i s t sa n i n t e g e r is m a l l e r t h a nns u c h t h a t l 十( i - 3 ) 1 + 。 ( j 一1 ) 1 “，w e h a v et h a t q 。( o ) 9 ，( 1 ) q 。( p ) q 。( p + 1 ) q 。( 1 竺j ) f o rs o m e ps i s o ，m i n q 。( t ) ，k = 0 ，l 2 ，l 孚) _ m i n 岛( o ) ，a 。( 1 字j ) ) 2 i f t h e r ee x i s t sn oi n t e g e ris m a l l e r t h a nns u c h t h a t1 + ( f 一3 ) 1 + “ ( f 1 ) 1 + 。，w e h a v e t h a t q n ( o ) q 。( 1 ) 曼曼q 。( 1 旦；三j ) s o ，m i n q 。( 女) ，k = 0 ，1 ，2 ，【2 手j ) = 岛( o ) b y f l o ww eh a v ef i n i s h e dt h ep r o o f o f t h e o r e m1 , 3 2 w ea l s on o t et h a t 岛( t n - 2 ) c o r _ r e s p o n d st ot h eg r a p hc o m p o s e d o f j n s t u b sf o rne v e n g ( n - 。3 ) c o r r e s p o n d st ot h eg r a p h c o m p o s e do f 字s t u b s a n da2 - s t a rf o rno d d ，a n dq ( o ) c o r r e s p o n d st ot h e ( n 一1 ) - s t a r l e x t r e m a lp r o b l e m so ng e n e r a lr a n d i di n d e xy i t i n gy a n g b e c a u s et h ec o m p l e t eg r a p hh a st h em a x i m u mv a l u ef o rb o t h r 一 a n d r 0 ，t h i s “a t u r a l l y s u g g e s t su st h a tf o r a l lc t , s u c ht h a t 一 f t 0 t h ec o m p l e t eg r a p hh a st h em a x i m u mv a l u e o f r u s ow eg e tt h ef o l l o w i n g t h e o r e m t h e o r e m1 1 2 l e tgb eng r a p ho f o r d e r 啊c o n t a i n i n gn oi s o l a t e dv e r t e x w h e n 一 0 l 0 w eh a v e 胚学， w i t he q u a l i t yi f a n d o n l yf i g i sac o m p l e