（运筹学与控制论专业论文）六角形系统的高阶连通指数.pdf

六角形系统的高阶连通指数 摘要 设g = m 功是个简单连通图，y 和e 分别为g 的顶点集和边 集m i l a nr a n d i 6 于1 9 7 5 年提出了图g 的一阶连通指数( 也称r a n d i d 指 数) t x ( g ) = ( d ( “) d ( ”) ) 一j 御占( g ) 其中d ( u ) 表示图g 中顶点u 的度数 连通指数是化学图论中非常重要的拓扑指数之一，它与有机物的 物理化学性质有着密切的联系，如沸点，表面积，能量值等等，且已在数 学和化学中得到了广泛的研究和应用后来，r a n d i d ，k i e r ，h a l l 等人进一 步推广，给出了高阶连通指数， k ( g ) - 。，互+ 。志l 2 “ + l v 1t 1 这里求和遍历图g 中所有长为h 的路并证实了高阶连通指数在物理和 化学中有着广泛的实际意义 对于六角形系统和苯撑，j r a d a ，o a r a u j o ，i g u t m a n 给出了它的一 阶连通指数的计算公式，得到了苯撑及其六角挤之间的关系；后来，j r a d a 又给出了六角形系统的二阶连通指数的一个计算公式本文我们进一步 研究这一图类的二阶和三阶连通指数，得到了以下结果t ( i ) 苯撑及其六角挤的二阶连通指数，以及二者之间的关系； “f ) 苯撑的三阶连通指数； ( i i i ) 六角链的三阶连通指数的极值情况 i 湖南师范大学2 0 0 7 届硕士学位论文 关键词：连通指数，六角形系统，苯撑，六角挤，六角链 h 六角形系统的高阶连通指致 a b s t r a c t l e tg = ( k e ) b e as i m p l ea n dc o n n e c t e dg r a p h 硝t ht h ev e r t e xs e tva n d t h ee d g es e te t h e nt h er a n d i 6i n d e x ( a l s oc a l l e dc o n n e c t i v i t yi n d e x ) o fag r a p h gi n t r o d u c e db ym i l a nl h n d i di n1 9 7 5i s ： x ( g ) = ( d ( 珏) d ( ”) ) 一 e e ( 研 w h e r ed ( u ) d e n o t e st h ed e g r e eo ft h ev e r t e x 让i ng c o n n e c t i v i t yi n d e xi so d eo ft h em o s ti m p o r t a n tt o p o l o g i c a li n d i c e si n c h e m i c a lg r a p ht h e o r y t h e r ei sag o o dc o r r e l a t i o nb e t w e e ni ta n ds e v e r a lp h y s i c o c h e m i c a lp r o p e r t i e so fa l k r n e s b o i l i n gp o i n t s ，s u r f a c ea r e a s ，e n e r g yl e v e l s ，e t c c o n n e c t i v i t yi n d e xh a sb e e n 埘d e l yi n v e s t i g a t e da n da p p f i e di nm a t h e m a t i c sa n d c h e m i s t r y a f t e r w a r d ，r a a d i 6 ，k i e r ，h a l lc o n s i d e r e dt h eh i g h e ro r d e rc o n n e c t i v i t y i n d i c e so fag e n e r a lg r a p hga s 啦。，磊- t h + ，焘1 1 2 + 1v。1 w w h e r e t h es u m m a t i o n i s t a k e n o v e ra l l p o s s i b l e p a t h s o f l e n g t h h o f g t h e y a p p r o v e d t h a th i g h e ro r d e rc o n n e c t i v i t yi n d i c e sh a v ew _ i d e l yp r a c t i c em e a n i n gi np h y s i c sa n d c h e m i s t r y f o rb e n z e n o i ds y s t e m sa n dp h e n y l e n e s ，j r a d a ，o a r a u j o ，i g u t m a nh a v e w o r k e do u tac o m p u t a t i o n a lf o r m u l a ，a n de s t a b l i s h e dar e l a t i o nb e t w e e nt h ec o n n e c - t i v i t yi n d i c e so fap h e n y l e n ea n dt h ec o r r e s p o n d i n gh e x a g o n a ls q u e e z e ；a f t e r w a r d ， j r a d ah a sw o r k e do u tac o m p u t a t i o n a lf o r m u l ao fb e n z e n o i ds y s t e m s i nt h i sp a - p e r ，w eg oo i lt oi n v e s t i g a t et h es e c o n do r d e ra n d t h i r do r d e rc o n n e c t i v i t yi n d i c e so f h e x a g o n a l8 ) 吲七m s ，a n dg e ts o m er e s u l t sb e l o w ： i i i 湖南师范大学2 0 0 7 届硬士学位论文 ( 1 ) s e c o n do r d e rc o n n e c t i v i t yi n d i c e so fp h e n y l e n e sa n di t sc o r r e s p o n d i n g h e ：c a g o n a ls q u e e z e s ，i n c l u d ear e l a t i o nb e t w e e nt h e m ； 0 f ) t h i r do r d e rc o n n e c t i v i t yi n d e xo fp h e n y l e n e s ； ( i i i ) t h eh e x a g o n a lc h a i n sw i t ht h ee x t r e m a l 蹦r do r d e rc o n n e c t i v i t yi n d e x k e y w o r d s ：c o n n e c t i v i t yi n d e x ，h e x a g o n a ls y s t e m ，p h e n y l e n e 。h e x a g o n a l i v 湖南师范大学学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独立 进行研究工作所取得的成果除文中已经注明引用的内容外，本论文不含 任何其他个人或集体已经发表或撰写过的作品成果对本文的研究做出 重要贡献的个人和集体，均已在文中以明确方式标明本人完全意识到本 声明的法律结果由本人承担， 学位论文作者签名：弓捉搪日期：7 0 0 7 年瑚；日学位论文作者签名：鸟饫牙霄 日期：年瑚；日 湖南师范大学学位论文版权使用授权书 本学位论文作者完全了解学校有关保留，使用学位论文的规定，同意学校保 留并向国家有关部门或机构送交论文的复印件和电子版，允许论文被查阅和借阅本 人授权湖南师范大学可以将学位论文的全部或部分内容编人有关数据库进行检索， 可以采用影印，缩印或扫描等复制手段保存和汇编本学位论文 本学位论文属于 1 、保密口，在年解密后适用本授权书 2 、不保密a 。 ( 请在以上相应方框内打“”) 日期t 刁年朝；旧 日期：撕7 篝9 加 | | 六角形系兢的高阶连通指教 第一章引言和文献综述 1 1 引言 图论已广泛应用于诸多学科领域，如计算机科学，通讯工程，物理学， 工业管理，心理学及社会学等，但是重要的应用领域应首推化学学科在 化学中，已有的应用涉及合成化学，聚合化学，量子化学及化学信息的存 储和检索等近年来，最大量的应用集中在定量结构活5 性质相关性 ( q s a r q s p r ) 的研究方面目前已涌现出了诸多q s a r q s p r 方法，其中 图论方法有其独特的优点，因为这类方法仅依赖于分子结构，即由结构图 可以直接衍生结构特征拓扑指数就是从化合物的结构图衍生出来的一 种数学不变量 大约在一百多年之前就引入了拓扑指数，至今已有2 0 0 多种被证实 在结构活性性质相关陡( q s a r q s p r ) 中非棠有用，这些指数中有些是 基于图中点的距离，有些是基于图中点的度数 在1 9 7 5 年，m r a n d i 提出了如下r a n d i d 指数( 也称为连通指数) 定义 为： ；x ( g ) = ：( d ( ) d ( ”) ) 一言 t e e ( g ) 其中d ( u ) 表示图g 中质点u 的度数，e ( g ) 为图g 中的边集r a n d i 证实 了他的指数与各种有机化合物的物理化学性质密切相关后来，这种结 构的搐述成为应用最多的的一种拓扑指数之一许多的文献【1 3 ，1 4 ，】5 】中 都探讨了它，像其它拓扑指数一样，r a n d i 6 指数引起了许多数学家和化学 家的极大关注出于拓展连通指数的应用的目的，r a n d i d ，k i e r ，h a l l 及其合 作者开始考虑图的高阶连通指数： 一 1 4 x ( c ) = ：f 兰亍一 u i u ：l 、d 1 1 l 这里求和遍历图g 中所有长为h 的路这种新的高阶连通指数立刻被成 1 湖南师范大学2 0 0 7 届硬士学位论文 功她广泛应用到许多物理，化学，生物性质中( 如沸点，溶解度，密度等) ， 其结果出现在大量的科学论文和两本著作中【1 0 ，2 7 】，其关于数学性质的 结果主要集中在【2 8 ，2 9 】 1 2 文献综述 自从r a n d i 6 提出了连通指数并发现它与各种有机化合物的物理一化 学性质密切相关之后，许多数学家和化学家都致力于研究它的一些特征 及一些特殊图类的连通指数主要的研究方向有。研究一些特殊图类的 连通指数；推广连通指数至广义的情形，研究一些特殊图类的广义连通 指数；研究一些特殊图类的高阶连通指数等 关于一阶连通指数，主要有以下一些图类的结果t ( 1 ) 对于n 阶连通图，b b o l l o b 应s 和p e r d s s 1 6 给出了下界； ( 2 ) 对于最小度为2 的图，c d e l o r m e ，o f a v a r o n 和d r a u t e n b a c h 【3 1 l 给 出了下界； ( 3 ) 对于树，路r 和星图品分别为最大值和最小值的囹； ( 4 ) 对于六角形系统和苯撑，j r 硝a ，o a r a u j o ，i g u t m a n 【3 6 】给出了它 的一阶连通指数的计算公式，得到了苯撑及其六角挤之间的关系； ( 5 ) 对于单圈图，g a o 和l uf 3 2 】给出了上界和下界； ( 6 ) 对于( ，m ) 化学图，o a r a u j o 和j a d e l a p e n a 【3 3 1 给出了上界，i g u t m a n 和o m f l j k o v i 6 3 4 】给出了下界； ( 7 ) 对于化学树，i g u t m a n ，o m i l j k o v i d ，g c a p o r o s s i 和p h a n s e n 【3 5 】给 出了前三大和前三小的情况 关于广义连通指数，主要有以下一些图类的结果： ( 1 ) 阶数为n 的图，x l i 和y y a n g 【1 7 给出了上界和下界； ( 2 ) 对于单圈图，x l i ，l w a n g 和y z h 觚g 【3 7 】给出了下界； 2 六角形系统的高阶连通指数 ( 3 ) 对于树，y h u ，x l i 和y y u a n 【1 8 ，1 9 】给出了上界和下界； ( 4 ) 对于( n ，m ) - 化学图，x l i ，x w a n g 和b w e if 2 0 给出了上界和下界； 而对于高阶连通指数，已有以下一些结果z ( 1 ) j r a d a 和o a r a u j o 【2 9 给出了似星树的高阶连通指数并证明两个 似星树同构当且仅当它们的高阶连通指数相等； ( 2 ) j r 们a 3 0 给出了六角形系统的二阶连通指数的一个计算公式 关于连通指数的其它一些结果见f 1 - 9 ，2 1 2 6 本文通过研究六角形系统中各种量之间的内在联系，并利用六角形 系统的边界特征来刻画其高阶连通指数，得到了以下结果： ( i ) 苯撑及其六角挤的二阶连通指数，以及二者之间的关系； ( i i ) 苯撑的三阶连通指数； ( t 税) 六角链的三阶连通指数的极值情况 从而在理论上说明了其二阶和三阶连通指数只与其边界结构有关 3 六角形系统的高阶连通指数 第二章苯撑及其六角挤的二阶连通指数 在这一章里，我们研究苯撑( p h ) 及其六角挤( h s ) 的二阶连通指数 通过计算，我们发现它们只与其边界结构有关类似于一阶连通指数，我 们也得到了苯撑与其六角挤的二阶连通指数之间的一个关系 2 1 定义 苯撑是一类由六圈和四圈的碳原子构成的化合物，每一个四圈( 正方 形) 邻接于两个六圈( 六角形) ，所以在苯撑中没有两个六角形是相邻的 一个苯撑的六角挤是由渺位六角形挤掉其四圈而得到的可见，对拥 有同样个数的六角形的苯撑及其六角挤之间存在一一对应一个具有h 个六角形的苯撑有h 一1 个正方形相应的，苯撵及其六角挤分别具有6 h 和4 h + 2 个点我们分别用p h 和h s 表示一个苯撵和与它对应的六角挤 它们的一个例子见图1 f i s s u r e b a yl c o v e p h i i s 图1 一个苯撑( p h ) 及其六角挤( h s ) 有关其它术语和符号，请进一步见【1 2 ，3 0 5 湖南师范大学2 0 0 7 届顼士学位论文 令p h 是具有n 个点，r n 条边和h 个六角形的苯撑我们用各种湾来 刻画苯撑及其六角挤的边界特征如果沿着一个苯撑的边界，出现度序 列为( 2 , 3 ，3 ，2 ) 的路径，则称之为一个f i s s u r e ；出现度序列为( 2 , 3 ，3 ，3 ，3 ，2 ) 的 路径，则称之为一个b a y ；出现度序列为( 2 , 3 ，3 ，3 ，3 ，3 ，3 ，2 ) 的路径，则称之为 一卟c o v e ；出现度序列为( 2 , 3 ，3 ，3 ，3 ，3 ，3 ，3 ，3 ，2 ) 的路径，则称之为一个右o r d ； 出现度序列为( 2 , 3 ，3 ，3 ，3 ，3 ，3 ，3 ，3 ，3 ，3 ，2 ) 的路径，则称之为一个l a g o o n 类似的， 对于其六角挤，沿着它的边界，出现度序列为( 2 , 3 ，2 ) 的路径，则称之为一 个f i s s u r e ；出现度序列为( 2 , 3 ，3 ，2 ) 的路径，则称之为一个b a y ；出现度序列 为( 2 ，3 ，3 ，3 ，2 ) 的路径，则称之为一个c o v e ；出现度序列为( 2 , 3 ，3 ，3 ，3 ，2 ) 的路 径，则称之为一个自o r d ；出现度序列为( 2 , 3 ，3 ，3 ，3 ，3 ，2 ) 的路径，则称之为一 个l a g o o n 具体情形见图l 及图2 p hh s 图2 一个具有l a g o o n 的苯撑( p h ) 及其六角挤( h s ) 在一个分子图中，各种边界特征f i s s u r e s ，b a y s ，c o v e s ，自o r d s 和l a g o o n s 的 数目分别记为，b ，a f 和工 f i s s u r e s ，b a y s ，c o v e s ，匀o r d s 和l a g o o n s 统称为入口令p h 或者h s 在边 界上的各种入e l 的总数为r ，即r = ，+ b + c + f + l ， 我们把另外一个参数b = b + 2 c + 3 f + 4 l 叫做b a yr e g i o n s p h 或者h s 中两个入口称为相邻当且仅当它们有一个共同的2 度点 邻接入口的个数记为a 6 六角形系统的高阶连通指致 2 2 苯撑及其六角挤的二阶连通指数 首先，由于苯撑中所有的点度数均为2 和3 ，所以p h 中长为2 的路符 合度序列( 2 , 2 ，2 ) ，( 2 , 2 ，3 ) ，( 2 , 3 ，3 ) ，( 3 , 2 ，3 ) 和( 3 , 3 ，3 ) 且容易看到p h 中不包含 度序列为( 2 , 3 ，2 ) 的路径，所以有 2 x ( p 日) = 丽1m 一+ 面1m 一+ 而1 ( m 啪+ 呦) + 击呦( 2 删 假设p h 包含n 个点，m 条边和h 个六角形，则根据其结构特征，有 竹= 6 h 而由欧拉定理可得；t l m + 2 h = 2 ， 所以 竹l = 8 h 一2 并且有 他+ 他= n 2 n 2 + 轨3 = 2 m 这里码表示图g 中度数为j 的点的个数j0 = 2 ，3 ) ，容易得出 耽= 2 h + 4 n 3 = 4 h 一4 引理2 1 令p h 表示含有n 个点和h 个六角形的苯撑，则有 ( 1 ) m + 2 m 3 船+ + 5 m 姚3 = 8 h 一2 ( 2 ) 7 0 , 3 3 + 1 7 7 , 3 2 3 + t n 2 3 + 抛2 2 2 2 3 = 6 h 一6 这里砜譬乡表示在p h 中度序列为( 3 ，之。二乡3 ) 的路径的数目 。 7 湖南师苑大学2 0 0 7 届硕士学位论文 证明( 1 ) 因为p h 中每条形如( 3 ，之。乡3 ) 的路径包含i + 1 条边，并 t 且p h 中不包含度序列为( 3 ，2 ，2 ，2 ，3 ) 的路径所以有 4 m = ( 1 ) m 咄 t = o 将m = 8 h 一2 代入原式计算即可得( 1 ) 式成立 ( 2 ) 因为p h 中度序列为( 3 ，3 ) 的路径含有i 个度为2 的点，所 以有 n 2 = ”幽= 2 h + 4 根据公式( 1 ) ，可以得到 哩2(汁1)一蚤“n3223iffi0i ” - - - - - o”b 1v = ( 8 h 一2 ) ( 2 + 4 ) = 6 h 一6 即( 2 ) 式成立 定理2 2 令p h 为含有h 个六角形，r 个入口和a 个邻接入口的苯撑 则有 删；兰每堂 + 萼竽r + 笔笋。+ ( 以一扣( z 2 2 ) 证明首先，通过计算可得：m 3 3 = 6 h r 一6 ，因为 m ；2 r m + 2 m 3 32 3 n 3 溅者， m = ( ，+ 3 b + 5 c + 7 f + 9 l ) + 2 ( h 一1 ) = ( r + 2 + 2 ( h 一1 ) 8 六角形系统的高阶连通指数 因为p h 中每一条度序列为( 3 ，3 ) 的边要么位于边界上，要么位于p h 的内 部根据 6 + r = ，+ 2 b + 3 c + 4 f + 5 l = ；啦= 2 h 一2 可以得到 m = r + 2 ( 2 h r 一2 ) + 2 一1 ) = 6 h r 一6 】 且 出 其次，由邻接入口得定义可知：m 。= n 再次，利用引理2 1 的结论和已得的m 及m 3 2 3 可以得出 m s 2 2 3 = 2 r - h - z ”7 , 3 2 2 2 2 3 = 一r + ；n + 2 慨= 2 m s 2 2 2 2 3 = 2 h 一2 r + a + 4 恸= 2 m s 2 驾+ 2 m a z z ；2 p a ) 另外，由于p h 中每个入口都有四条度序列为( 2 ，3 ，3 ) 的路径，可以得 m 2 4 r 要计算m 3 3 3 ，首先要注意到p h 中每条度序列为( 3 ，3 ，3 ) 的路径或者位 于同一个六角形上，或者位于同一个正方形上，或者一条边位于六角型上 一条边位于正方形上，于是有 t t t 3 3 3 = 6 h 一6 r n 3 2 2 一4 m 3 2 2 3 3 m 3 船+ 4 ( h 一1 ) + 2 b + 4 5 + 6 f + 8 l = 8 h 一2 r + 2 6 8 1 2 h4 r1 2 将所求得的”锄边代入公式( 2 2 1 ) 即可证明定理2 2 9 湖南师范大学2 0 0 7 届顼士学位论文 令s 为具有n 个点，h 个六角彤，r 个入口，f 个f i s s u r e 以及a 个邻援入 口的苯环系统，r a d a 3 0 】证明了 2 x ( s ) ：丁4 5 等磊+ 兰竽r + 骂竽， + 掣口+ 下3 4 5 - 4 v 5 1 2 2 3 、) + 1 广o + 广 对于p h 的六角挤h s ，有以下结论： 引理2 3 ( 3 0 ) 令h s 为具有h 个六角形，r 个入口，f 个f i s s u r e 以及8 个邻接入口的苯撑的六角挤则有 ：x ( 日s ) ：华九+ 丁3 4 5 - 2 4 5 r + 掣n + 堕1 巡8 ，+ ( 以一竽) ( 2 2 由n = 4 h + 2 及公式( 2 3 ) 可得 对比定理2 2 ，苯撑p h 及其六角挤h s 的二阶连通指数之间有以下联 系： 推论2 4 设苯撑p h 及其六角挤h s 含有h 个六角形，f 个f i s s u r e ，则 。舻= 2 x ( h 趾学h 一竽，一学 推论2 4 给出了苯撑及其六角挤的二阶连通指数之间的关系，并进一 步说明，对于六角形数目和f i s s u r e 数目相同的任意两个苯撑，其二阶连 通指数相同当且仅当对应的六角挤的二阶连通指数相同 1 0 六角形系统的高阶连通指数 第三章苯撑的三阶连通指数 本章，我们利用苯撑的边界结构给出了它的三阶连通指数的一个计 算公式，进一步证明了苯撑的三阶连通指数也只与它的边界结构有关 首先，由于苯撑中所有的点度数均为2 或3 度，所以其长为3 的路径 度序列可以为( 2 , 2 ，2 ，2 ) ，( 2 , 2 ，2 ，3 ) ，( 2 , 2 ，3 ，3 ) ，( 3 , 2 ，2 ，3 ) ，( 2 , 3 ，3 ，2 ) ，( 2 , 3 ，3 ，3 ) ，( 3 , 2 ，3 ，3 ) 或( 3 , 3 ，3 ，3 ) 容易知道p h 中不含有度序列为( 2 , 2 ，3 ，2 ) 和( 2 , 3 ，2 ，3 ) 的路径因 此有 111 3 x ( p 日) 2 i 慨+ 赢恸+ ；( 呦+ m 3 2 + ) 11 + ；( m 2 3 3 3 + m 3 2 ) 4 - 言m 3 3 3 a ( 3 0 1 ) o v u o 这里仃“表示度序列为( i ，j ，女，z ) 的路径数目接下来，我们将证明p h 的 三阶连通指数完全由 ，r ，和。决定 令p h 为有n 个点，i l l 条边和h 个六角形的苯撑，则有 因为他一m + 2 h = 2 ，所以有 n = 6 h m = 8 h 一2 并且 他+ 他= 礼 2 地+ 3 n s = 2 m 这里q 表示图g 中度为j 的点的数目0 = 2 ，3 ) ，容易看出 砌= 2 h + 4 ，1 3 = 4 h 一4 引理3 1 令p h 为有个点，h 个六角形的苯撵( h 2 ) 则有 1 1 湖南师范大学2 0 0 7 届硕士学位论文 ( 1 ) ，7 l + 2 r a m + 3 3 2 + 5 ”船= 8 h 一2 ( 2 ) + n 9 , 3 2 3 + f t t 3 2 2 3 + 1 t 1 3 2 2 2 2 326 h 一6 这里m 3 。表示p h 中度序列为( 3 ，2 ，2 ，3 ) 的路径的数目 丫丫一 证明( 1 ) 因为p h 中的每条度序列为( 3 ，! ，多3 ) 的路径含有t + 1 i 条边并且p h 没有度序列为( 3 ，2 ，2 ，2 ，3 ) 的边因此有 4 m = ( 1 ) m 幽 i = 0 再根据m = 8 h 一2 可得公式( 1 ) ( 2 ) 因为p h 的每条边( 3 ，之o d 3 ) 含有i 个度数为2 的点所以有 i 运用公式( 1 ) ，可以得到 4 啦= i ”世= 2 h + 4 = l 4 44 m 3 2 ：圣3 20+1)m32u3一弘171,3v2,23i-oi = oi = 1丫 ，_ = ( 8 h 一2 ) 一( 2 + 4 ) = 6 h 一6 即( 2 ) 式成立 定理3 2 令p h 表示具有h 个六角形，r 个入口和a 个邻接入口的苯 撑 3 _ ，n 。1 0 9 + 2 娟。1 4 瓶一3 1 2 7 - l o j g a x ( p 日) = 三! 旦；竽 + 掣r 一7 2 。 + 可5 - 2 v f 6 卜坠1 堂8 ( 3 0 2 ) 证明首先，通过计算可以得到仃均= 6 h r 一6 六角形系统的高阶连通指致 因为 m = 2 r m + 2 m 格= 3 n s 【或者， m = ( ，+ 3 b + 5 c + 7 f + 9 l ) + 2 ( h 一1 ) = ( r + 2 6 ) + 2 ( h 一1 ) 因为p h 中的每一条度序列为( 3 ，3 ) 的边或者位于边界上或者位于内部 由于 b + r = ，+ 2 b + 3 c + 4 f + 5 l = ；竹3 = 2 h 一2 因此有 m 3 3 = r + 2 ( 2 h r 一2 ) + 2 ( h 一1 ) = 6 h r 一6 】 其次，显然有m n 。= o 利用引理1 和m 3 。及r n 3 2 3 ，可以得到 7 n 3 2 2 3 = 2 r h 一吾3 n 一2 呦：h r + ；d + 2 所以 1 1 2 2 2 2 = m 3 2 2 2 = _ i l r + ：口+ 2 r n - n 2 3 = 2 m 3 2 2 ：n 3 = 2 h 一2 r + a + 4 再次，由于长为3 的度序列为( 2 , 2 ，3 ，3 ) 的路径只可能包含于长为5 的度序列为( 3 , 3 ，2 ，2 ，3 ，3 ) 或( 3 , 3 ，2 ，2 ，2 ，2 ，3 ，3 ) 的路径中，并且m 3 3 2 2 3 3 = m 3 2 2 3 ， m 稿2 2 2 猫= t n 3 2 2 2 2 3 ，所以 m 铭= 4 m 3 3 2 2 站+ 出n 3 3 2 露2 = 4 m 宝n s + 4 m 3 2 2 2 = 4 ( r 一口) 度序列( 3 , 2 ，3 ，3 ) 中的2 度点必位于两个相邻的入口上，因此有 7 7 3 2 3 3 。4 a 1 3 湖南师范大学2 0 0 7 届硕士学位论文 一条长为3 且度序列为( 2 , 3 ，3 ，2 ) 的路径或者为一i s s u r e ，或者位于六 角形中度序列为( 2 ，3 ，3 ，2 ，3 ，3 ) ( 这里2 度点必是两个相邻的入口上的) 的路 径上，或者位于具有度序列为( 3 , 2 ，2 ，2 ，2 ，3 ) 的六角形上所以 m = ，+ 口+ m 黝= ，+ 。+ 一r + ；n + 2 要计算m 2 3 3 3 ，我们注意到一条长为2 且度序列为( 2 , 3 ，3 ) 的路径包含 于长为3 的度序列为( 2 , 2 ，3 ，3 ) ，( 3 , 2 ，3 ，3 ) ，( 2 , 3 ，3 ，2 ) 或( 2 , 3 ，3 ，3 ) 的路径上，如图 3 所示 且 因此 ，2 ( 2 ) ( 3 ) 2 ( 3 1 一一一l 一 233 、 、2 ( 3 ) ( 3 ) 图3 这就表示 t n 2 2 3 3 + f r t 3 2 3 3 + 2 m 2 3 3 2 + m 2 3 3 323 “2 3 3 ”咖= 1 2 r 一( 2 r + 2 ，+ 2 + 3 0 + 4 ) = l o t 一2 ，一2 一3 0 一4 相似的，我们有 ”2 3 + 2 m = 4 嚣3 r f t 3 3 3 3 = ( 5 0 h 一2 6 r + 3 a + 2 ，一4 4 ) = 2 5 h 一1 3 r + ；o + ，一2 2 因此定理3 2 可以由将求出的各边”鲥代入等式( 3 0 1 ) 得到 1 4 六角形系统的高阶连通指数 第四章六角链的三阶连通指数 本章我们先给出计算六角链的三阶连通指数的一个递推公式，然后 利用这个公式确定了六角链的三阶连通指数的最大值和最小值，并刻画 了相应的极值图的特征 4 1 定义 一个六角形系统是一个没有割点的有限连通平面图，它的每一个内 部区域是由一个边长为1 的正则六边形围成的六角形链是每一个六角 形都只最多邻接于两个六角形的六角形系统一些六角形链的例子见图 4 ( i ) ah e x a g o n a lc h a i ni - 1 8 ( i i ) ah n e a rc h a i n 工6 ( n i ) 82 i 争。a go h a i n 历 图4 不同类型的六角链 容易知道任何一个有n + 1 个六角形的六角链以+ 。能通过一个具有 n 个六角形的六角链巩粘上一个六角形而得到，正是基于此，任何一个 六角链可以通过递推的构造得到 1 5 湖南师范大学2 0 0 7 届硬士学位论文 有三种办法可以将一个六角形粘到一个具有n 个六角形的六角链风 上； ( i ) 如果7 l ，l + 。在直线z 上，就叫做型粘合； ( i i ) 如果k ，在直线z 的左边，就叫做伊型粘合； ( i i i ) 如果k + 。在直线f 的右边，就叫做t 型粘合 这里：指连接六角形k l 和k 中心的直线任何一个六角链风m 2 ) 可以通过飓一步步的粘结而成，每一步都是一个乒型粘合，这里日 o ，a 7 ) 令h ( 0 。，如，艮) 为由飓依次经过口。型，如型，如一型粘合得 到的具有n + 2 个六角形的六角链则日( a ，o ) 叫做线性链厶+ 2 日( 卢，* 卢，7 ，) 或h ( 7 ，卢，仉卢，) 叫做z i g - z a g 链磊+ 2 令 一f a ， 9 = p ， 【，y ， 贝4h 0 1 ，如，如) 皇h ( 7 1 ，瓦，爵) 式 i f 口= q ： i f 日= 饿 i f 占= 口 4 2 六角链的三阶连通指数的递推公式 在这一节中，我们给出一个计算六角形链的三阶连通指数的递推公 令碥+ 3 = h ( 0 l ，如，如，i ) 为如图5 的个六角链 1 6 六角形系统的高阶连通指数 wi 口! 磅f l y c o 令。 z 、 j 7 j ( 5 ) 跽曙 ( ；) ( 9 ) 图5 则由凰+ - 通过粘结两个六角形得到风+ s 有以下五种情况： 情况i 如= 以+ ，= a 此时风+ 3 是由日0 2 经过一个* 型粘合得到 的( 见图5 ( 1 ) ) 长为3 的道路w x y z ，w a l a 2 z ，卸8 l 啦6 2 ， u l a l b w l ，x y z a 2 ，z 。l a 2 ， z o l h ，y x w a l ，y z a 2 a 1 ，y z a 2 b 2 ，z a 2 a l b l ，z 眈6 2 q 是新增加的除了d l c l b l d l ，c 2 c i b l a l ， 如c 2 6 2 啦，c i c 2 b 2 a 2 ，c l b l a l 勉，c 2 b 2 a 2 a 1 和b l a l 0 2 6 2 ，矾+ 3 中其它的长为3 的道路与 巩+ 2 是相同的令m ( p ) 和矸，2 ( p ) 分别为玩+ 3 和风+ 2 中道路p = u 1 v 2 v 3 v 4 的权重蕊丽乖毓 表1 风+ 3 中一些长为3 的道路的权重 1 7 湖南师范大学2 0 0 7 届硕士学位论文 叫z y z口l a 2 zw 0 1 a 2 6 2l l j a l b l c lz y z a 2 o 叫0 1 0 2 1llll 4 6666 z w o l 6 1 y x 叫a l y z a 2 a l暑，z 口2 6 2z a 2 a l b l z a 2 b 2 c 2 1 lll i 蕊i 刁 866 d l o l b l a l 也o l b l a td 2 c 2 6 2 啦c l c 2 b 2 a 2c l b l a l a 2晚b 2 a 2 a 1b l a l a 2 6 2 i l111 1 6 i 孺 63 bi 孺 6 i lll 1 i 蕊 6i 蕊6元虿 4 由三阶连通指数的定义，我们有 r 3 ( h + 3 ) = r 3 ( 巩+ 2 ) + ；+ ；插 情况i i 如= o 且艮+ 1 = 口或p 。+ l = 7 此时日n + 3 是由巩+ 2 通过一个 伊型或者一个t 型粘合而成的( 见图5 ( 2 ) 或( 3 ) ) 类似的，有： 有： 剐3 ) = r 3 ( h + 2 ) + ；+ 丽1 7 而 情况i i i 以= 卢或者氏= ，y 且如+ l = o ，见图5 ( 4 ) 或( 7 ) 类似的，有： 凰( 巩+ 3 ) = 飓( 风+ 2 ) + l + 蓦而 情况如= 如+ l = 卢或者艮= 1 = ，y ，见图5 ( 5 ) 或( 8 ) 类似的， i ft h ed e g r e eo f d li st w o ； i f t h ed e g r e eo f d l i 8 t h r e e 六角形系统的高阶连通指教 情况v = p 且如+ l = 7 或者以= 7 且l = 卢，见图5 ( 6 ) 或( 9 ) 类 似的，有， 风( a ) = r 3 ( 风+ 2 ) + 西2 5 + ；砺 综合各种情况，可以得到下面的递推公式， 定理4 1 令凰，+ 3 = h ( e l ，如，如，以+ 1 ) 和风+ 2 = h ( e l ，如，以) 为 六角形链则 怒( 磊+ 3 ) = r 3 ( 玩神) + f ；+ ；怕， l5 + 器怕， 1 + 嚣瓶 i ；+ 瓶或西1 7 + 云怕， 【器+ ；怕， 如= 以+ l = q “= o 且如+ 1 = 卢或l = ，y ； 靠= 卢或气= 7 且钆+ l = 口； 靠= 靠+ 1 = p 或靠= 靠+ l = 7 ； 氏= 卢且+ l = 7 或钆= 7 且以+ l = 口 4 3 六角链的三阶连通指数的极值情况 在这一节中，我们将给出六角链的三阶连通指数最大最小的情况并 刻画出极值图 定理4 2 令凰+ 2 = 日( 口。，如，钆) 为具有n + 2 个六角形的六角链 则 ( i ) 见( 段+ 2 ) 下8 “+ 1 1 1 - 下2 n + 6 娟等号成立当且仅当( 口l ，如，“) = ( q ，q ，) ， 即风帕是一个线性链厶+ 2 ； ( i i ) 风( 风+ ：) 鼍产+ 学、，信等号成立当且仅当( 日l ，如，靠) = 够，m 反7 ，) 或( 1 ，成夙) ，即风+ 2 是个z i g - z a g 链磊+ 2 1 9 湖南师范大学2 0 0 7 届硬士学位论文 证明，由定理4 1 及r 3 ( 日2 ) = 譬+ i 砺，可知 忍( 厶+ 2 ) = 1 2 + 玺怕 局( 磊柏) = 墅警堡+ 垒乒、，氤 然后，对n 利用递推的方法，可以证明岛( k + 。) 岛( 峨+ 2 ) 尼( 磊+ 。) ， 左边( 右边) 等号成立当且仅当风+ 2 是厶+ 2 ( 或者磊+ 。) 可以直接计算得到t 忍( 玩) = 詈+ ；怕 啪，= 矧三薏淼= ；+ 怕 i 风( 日( o ，a ) ) = ；+ 訾 5 j r 3 ( h ( a ，p ) ) = 风( 日( n ，们) = 两7 1 + 墓瓶 r 3 ( h 4 ) = 昆( 月( 卢，n ) ) = r 3 ( h ( 7 ，a ) ) = 两7 1 + 嚣怕 ir 3 ( h ( z ，y ) ) = r 3 ( h ( 7 ，卢) ) = 譬+ 竽怕 【昆( 日，卢) ) = 尼( 点r ( 7 ，7 ) ) = 嚣+ 2 、石 及 r 3 ( 月( q ，o ) ) r s ( 日( d ，卢) ) = r 3 ( h ( a ，7 ) ) = 风( 日( 卢，a ) ) = r a ( h ( 7 ，q ) ) r 3 ( 日( p ，卢) ) = r s ( 日( ，y ，7 ) ) 忌( 日( 屈，y ) ) = 岛( 日( 7 ，卢) ) 所以，当 = 0 ，1 ，2 时定理成立 假设当n 和几一1 时定理成立 2 ) ，即： 飓( 厶+ 。) sr 3 ( 凰+ ：) 岛( 磊+ 2 ) 左边( 右边) 等号成立当且仅当砜+ 2 为工。+ 。( 或者瓦+ 2 ) ，凰( k + - ) r s ( 且r 卅t ) 昆( 磊+ 。) 左边( 右边) 等号成 立当且仅当壕+ t 为厶+ z ( 或者磊+ - ) 令风+ 3 = ( 0 1 ，0 2 ，靠，艮+ - ) 一个具有n + 3 个六角形的六角链因 为有， 2 0 六角形系统的高阶连通指数 ；+ ；瓶 + 芸瓶 ；+ ；掂 苦+ 矗掂 嚣+ ；瓶 ；+ 芸擂 由定理4 1 ，可以得到 ( i ) 凡( 风+ 3 ) 2 飓( 风+ 2 ) + i 4 + ；瓶等号成立当且仅当如= 如+ 1 = n 由归纳假设，r 3 ( 风+ 。) r 3 ( l 。+ 。) 等号成立当且仅当以+ 2 为l ”：，所以， 凰( 风+ 3 ) 尼( k + 3 ) 等号成立当且仅当以+ 3 为厶+ 3 凰( h 1 ”2 ) + ( ；+ 岩洞，当氏= q ； r 3 ( h + 2 ) + ( 嚣+ ；怕) ，当e n = p 或，y r 3 ( h 。+ 1 ) + ( 1 + 等 劭+ ( ；+ 嚣怕) ，当氏= c t ； r z ( h + 1 ) + 2 ( 嚣+ ；娟) ， 当如= p 或7 因为( 1 + 嚣怕) + ( 5 + 器怕) 2 ( 嚣+ ； 砷，有 风( 风+ 3 ) s 凡( 风+ - ) + 2 ( 器+ ；、，回等号成立当且仅当( 靠- i ，艮，钆+ 1 ) = ( p ，1 ，p ) 或( 7 ，卢，7 ) 由归纳假设，r 3 ( 以+ 1 ) r 3 ( z + - ) 等号成立当且仅当凰+ - 为磊”所 以，r 。( 巩+ 3 ) r 3 ( 磊+ 。) 等号成立当且仅当风+ 3 为z n + 3 因此，由归纳假设当n 0 时结论成立 2 1 ，f1，(。l 一 一 心 ，l 黾 六角形系统的高阶连通指敷 第五章结语 本文是在j r a d a 等人的研究基础上，利用图的边界特征( 即各种不 同酌湾) ，考虑六角形系统中苯撑及其六角挤的二阶连通指数和三阶连通 指数，并考虑了六角链的三阶连通指数的极值情况，从而在理论上说明 了其二阶和三阶连通指数只与其边界结构有关我们也曾考虑过用六角 形系统的其它外部特征来刻画其连通指数，发现结果殊途同归，另外还 考虑过一般六角形系统的三阶连通指数，发现用现有的几种边界特征不 能完全刻画，需要添加其它的外部特征因此关于一般六角形系统的高 阶连通指数的研究有一定的难度 关于其它图类的高阶连通指数，我们还在进一步研究 2 3 六角形系统的高阶连通指教 参考文献 【1jx n ，h z h a o ，t r e e sw i t ht h ef i r